"""Exact, offline teaching implementations for fine-grained reduction interfaces.
None is positive infinity. Algorithms here are elementary reference solvers, not
implementations of a subcubic breakthrough. The online harness enforces the stated
pull/submit API; it is not a security sandbox against Python reflection.
Python standard library only. Public constructed test cases. Explicit checks run -O.
"""
from fractions import Fraction
from collections import deque
from pathlib import Path
import json,random,itertools

def check(condition,message):
    if not condition: raise ValueError(message)

def matrix(a):
    check(type(a) is list,'matrix is a list')
    n=len(a)
    check(all(type(r) is list and len(r)==n for r in a),'square matrix')
    check(all(x is None or type(x) is int for r in a for x in r),'integer or infinity')
    return n

def product(a,b):
    n=matrix(a);check(matrix(b)==n,'same square shape')
    c=[[None]*n for _ in range(n)];w=[[None]*n for _ in range(n)];tests=0
    for i in range(n):
        for j in range(n):
            for k in range(n):
                tests+=1
                if a[i][k] is None or b[k][j] is None:continue
                z=a[i][k]+b[k][j]
                if c[i][j] is None or z<c[i][j]:c[i][j]=z;w[i][j]=k
    return c,w,tests

def product_via_finite(a,b):
    n=matrix(a);check(matrix(b)==n,'same square shape')
    bound=max([0]+[abs(x) for t in (a,b) for r in t for x in r if x is not None])
    sentinel=3*bound+1
    aa=[[sentinel if x is None else x for x in r] for r in a]
    bb=[[sentinel if x is None else x for x in r] for r in b]
    c,_,tests=product(aa,bb)
    return [[None if x>2*bound else x for x in r] for r in c],sentinel,tests

def normalize(n,edges):
    check(type(n) is int and n>=0,'vertex count')
    d=[[None]*n for _ in range(n)];base=[[None]*n for _ in range(n)];byid={}
    for i in range(n):d[i][i]=0
    for e in edges:
        check(type(e) in (tuple,list) and len(e)==4 and all(type(x) is int for x in e),'integer arc tuple')
        ident,u,v,c=e
        check(ident not in byid and 0<=u<n and 0<=v<n,'unique arc ID and endpoints')
        byid[ident]=tuple(e)
        if d[u][v] is None or c<d[u][v] or (c==d[u][v] and base[u][v] is not None and ident<base[u][v]):
            d[u][v]=c;base[u][v]=ident
    return d,base,byid

class Closure:
    def __init__(self,n,edges):
        d,self.base,self.byid=normalize(n,edges);self.n=n;self.levels=[d];self.splits=[];self.caps=[1];self.product_tests=0
        while self.caps[-1]<n:
            d,k,tests=product(d,d);self.levels.append(d);self.splits.append(k);self.caps.append(2*self.caps[-1]);self.product_tests+=tests
        self.d=d;self.negative_vertex=next((v for v in range(n) if d[v][v]<0),None)
    def walk(self,u,v):
        check(type(u) is int and type(v) is int and 0<=u<self.n and 0<=v<self.n,'walk endpoints')
        if self.d[u][v] is None:return None
        out=[];todo=[(len(self.levels)-1,u,v)]
        while todo:
            level,i,j=todo.pop()
            if not level:
                e=self.base[i][j]
                if e is not None:out.append(e)
                else:check(i==j,'finite base witness')
            else:
                k=self.splits[level-1][i][j];check(k is not None,'finite split witness')
                todo.append((level-1,k,j));todo.append((level-1,i,k))
        self.verify_walk(u,v,out,self.d[u][v]);return out
    def verify_walk(self,u,v,ids,cost):
        point=u;total=0
        for ident in ids:
            _,x,y,w=self.byid[ident];check(x==point,'arc continuity');point=y;total+=w
        check(point==v and total==cost,'walk cost and endpoint')
        check(len(ids)<=self.caps[-1],'bounded walk length')
    def summary(self):
        k=self.negative_vertex
        return dict(status='NEGATIVE_CYCLE' if k is not None else 'DISTANCES',caps=self.caps,matrices=self.levels,
                    product_tests=self.product_tests,negative_witness=None if k is None else dict(vertex=k,cost=self.d[k][k],arc_ids=self.walk(k,k)))

def floyd(n,edges):
    d,_,_=normalize(n,edges)
    for k in range(n):
        for i in range(n):
            if d[i][k] is None:continue
            for j in range(n):
                if d[k][j] is not None:
                    z=d[i][k]+d[k][j]
                    if d[i][j] is None or z<d[i][j]:d[i][j]=z
    return d

def product_via_apsp(a,b):
    n=matrix(a);check(matrix(b)==n,'same shape');edges=[]
    for i in range(n):
        for j in range(n):
            if a[i][j] is not None:edges.append((len(edges),i,n+j,a[i][j]))
            if b[i][j] is not None:edges.append((len(edges),n+i,2*n+j,b[i][j]))
    d=floyd(3*n,edges)
    return [r[2*n:3*n] for r in d[:n]],dict(vertices=3*n,arcs=edges)

def bool_matrix(m):
    n=matrix(m);check(all(type(x) is int and x in (0,1) for r in m for x in r),'Boolean matrix');return n

def vector(v,n):check(type(v) is list and len(v)==n and all(type(x) is int and x in (0,1) for x in v),'Boolean vector')
def matvec(m,v):return [int(any(x and y for x,y in zip(r,v))) for r in m]

class Protocol:
    def __init__(self,m,provider):
        self.m=m;self.n=bool_matrix(m);self.provider=provider;self.index=0;self.pending=None;self.last=None;self.events=[]
    def pull(self):
        check(self.pending is None,'must submit complete answer before next vector')
        check(self.index<self.n,'all rounds exhausted')
        v=self.provider(self.index,self.last);vector(v,self.n);self.pending=list(v)
        self.events.append(dict(event='reveal',round=self.index,vector=list(v)));return list(v)
    def submit(self,answer):
        check(self.pending is not None,'no pending round');vector(answer,self.n)
        check(answer==matvec(self.m,self.pending),'incorrect complete product')
        self.events.append(dict(event='submit',round=self.index,answer=list(answer)))
        self.last=list(answer);self.pending=None;self.index+=1

class Reach:
    """Fixed source s=0, columns 1..n, rows n+1..2n. Generic BFS query baseline."""
    def __init__(self,m):
        self.n=bool_matrix(m);self.adj=[[] for _ in range(2*self.n+1)];self.active=set()
        for i,r in enumerate(m):
            for j,x in enumerate(r):
                if x:self.adj[1+j].append(1+self.n+i)
        self.updates=0;self.queries=0;self.edge_scans=0;self.input_cells=self.n*self.n
    def replace_vector(self,v):
        vector(v,self.n);changed=[]
        for j,x in enumerate(v):
            present=j in self.active
            if bool(x)!=present:
                if x:self.active.add(j)
                else:self.active.remove(j)
                self.updates+=1;changed.append(dict(column=j,action='insert' if x else 'delete'))
        return changed
    def query(self,i):
        check(0<=i<self.n,'row query');self.queries+=1;target=1+self.n+i;seen={0};q=deque([0])
        while q:
            u=q.popleft()
            if u==target:return 1
            for v in ([1+j for j in sorted(self.active)] if u==0 else self.adj[u]):
                self.edge_scans+=1
                if v not in seen:seen.add(v);q.append(v)
        return 0

def online(m,protocol,block=None):
    n=bool_matrix(m);check(protocol.n==n,'protocol shape')
    b=max(1,n) if block is None else block;check(type(b) is int and b>=1,'block size')
    g=(n+b-1)//b;structures={};transcript=[];merges=0
    for x in range(g):
        for y in range(g):
            part=[[m[x*b+i][y*b+j] if x*b+i<n and y*b+j<n else 0 for j in range(b)] for i in range(b)]
            structures[x,y]=Reach(part)
    for t in range(n):
        v=protocol.pull();out=[0]*n;rows=[]
        for x in range(g):
            for y in range(g):
                obj=structures[x,y];segment=[v[y*b+j] if y*b+j<n else 0 for j in range(b)]
                updates=obj.replace_vector(segment);partial=[obj.query(i) for i in range(b)]
                for i,z in enumerate(partial):
                    merges+=1
                    if x*b+i<n:out[x*b+i]|=z
                rows.append(dict(block=[x,y],updates=updates,partial=partial))
        protocol.submit(out);transcript.append(dict(round=t,vector=v,blocks=rows,answer=out))
    check(protocol.pending is None and protocol.index==n,'all rounds submitted')
    return dict(block_size=b,block_count=g*g,graph_vertices_per_block=2*b+1,input_cells=sum(o.input_cells for o in structures.values()),
                updates=sum(o.updates for o in structures.values()),queries=sum(o.queries for o in structures.values()),merges=merges,
                actual_baseline_edge_scans=sum(o.edge_scans for o in structures.values()),transcript=transcript,protocol=protocol.events)

def budget(preprocess_exponent,operation_saving):
    c=Fraction(preprocess_exponent);eps=Fraction(operation_saving)
    check(c>=2 and 0<eps<=1,'c>=2 and 0<epsilon<=1')
    alpha=1/(2*(c+1));pre=2+alpha*(c-2);ops=3-alpha*eps;merge=3-alpha;gap=(3-max(pre,ops,merge))/2
    check(gap>0,'positive exponent margin')
    return {k:str(v) for k,v in dict(c=c,epsilon=eps,alpha=alpha,preprocess=pre,operations=ops,merge=merge,after_log_margin=gap).items()}

def tests():
    rng=random.Random(121009);counts=dict(matrix_products=0,acyclic_graphs=0,negative_graphs=0,online_sequences=0)
    for n in range(6):
        for _ in range(60):
            a=[[None if rng.randrange(4)==0 else rng.randrange(-8,9) for _ in range(n)] for _ in range(n)]
            b=[[None if rng.randrange(4)==0 else rng.randrange(-8,9) for _ in range(n)] for _ in range(n)]
            c,_,_=product(a,b);check(product_via_apsp(a,b)[0]==c,'three-layer product');check(product_via_finite(a,b)[0]==c,'finite sentinel');counts['matrix_products']+=1
            edges=[]
            for i in range(n):
                for j in range(i+1,n):
                    if rng.randrange(3):edges.append((len(edges),i,j,rng.randrange(-8,9)))
            z=Closure(n,edges);check(z.negative_vertex is None and z.d==floyd(n,edges),'DAG closure')
            for i in range(n):
                for j in range(n):z.walk(i,j)
            counts['acyclic_graphs']+=1
    for n in range(1,6):
        for _ in range(60):
            edges=[]
            for i in range(n):
                for j in range(n):
                    if rng.randrange(3)==0:edges.append((len(edges),i,j,rng.randrange(-3,5)))
            z=Closure(n,edges);d=floyd(n,edges);negative=any(d[i][i]<0 for i in range(n))
            check((z.negative_vertex is not None)==negative,'negative diagonal equivalence')
            if negative:k=z.negative_vertex;z.walk(k,k)
            else:check(z.d==d,'general closure')
            counts['negative_graphs']+=1
    for n in range(6):
        for _ in range(40):
            m=[[rng.randrange(2) for _ in range(n)] for _ in range(n)];vs=[[rng.randrange(2) for _ in range(n)] for _ in range(n)]
            for b in (1,2,3,max(1,n)):
                p=Protocol(m,lambda t,last:vs[t]);r=online(m,p,b)
                check(r['queries']==n*((n+b-1)//b)**2*b,'query count');check(r['merges']==r['queries'],'merge count')
                check(r['updates']<=r['queries'],'update upper bound')
                counts['online_sequences']+=1
    for c in (2,3,5,100):
        for e in ('1','1/2','1/100'):budget(c,e)
    p=Protocol([[1]],lambda t,last:[1]);p.pull()
    try:p.pull()
    except ValueError:pass
    else:raise ValueError('lookahead accepted')
    p.submit([1]);check(len(p.events)==2,'lookahead did not expose new vector')
    return counts

def migrations(m,vectors):
    aa=[[None,-10],[None,None]];bb=[[-10,None],[None,0]]
    correct=product(aa,bb)[0];finite,h,_=product_via_finite(aa,bb)
    wrong=product([[20 if x is None else x for x in r] for r in aa],[[20 if x is None else x for x in r] for r in bb])[0]
    wrong=[[None if x>=20 else x for x in r] for r in wrong]
    check(correct==finite and wrong!=correct,'sentinel counterexample')
    big=(1<<200)+1;large_a=[[None,-big],[None,None]];large_b=[[-big,None],[None,0]]
    large,lh,_=product_via_finite(large_a,large_b);check(large==product(large_a,large_b)[0],'large integer sentinel')
    changed=[r[:] for r in m];changed[2][1]=1
    variation=online(changed,Protocol(changed,lambda t,last:vectors[t]));column=[r['answer'][2] for r in variation['transcript']]
    check(column==[0,1,0,1],'fixed matrix migration')
    stale=Reach(m);stale_rows=[]
    for v in vectors:
        accumulated=[int(j in stale.active or bool(v[j])) for j in range(len(m))]
        stale.replace_vector(accumulated);stale_rows.append([stale.query(i) for i in range(len(m))])
    expected=[matvec(m,v) for v in vectors];check(stale_rows[1]!=expected[1],'insert-only mutant')
    parity=[sum(x*y for x,y in zip(row,vectors[0]))%2 for row in m]
    transpose=matvec([list(r) for r in zip(*m)],vectors[0])
    check(parity!=expected[0] and transpose!=expected[0],'wrong algebra and transpose')
    invoked=[]
    def provider(t,last):invoked.append(t);return vectors[t]
    p=Protocol(m,provider);p.pull()
    try:p.pull()
    except ValueError as e:blocked=str(e)
    else:raise ValueError('missing online gate')
    check(invoked==[0],'no future provider call before submit')
    p.submit(expected[0]);p.pull();check(invoked==[0,1],'next reveal after submit')
    return dict(sentinel=dict(correct=correct,finite=finite,h=h,wrong_h20=wrong),large_integer=dict(magnitude=str(big),sentinel=str(lh),sentinel_bits=lh.bit_length(),product=large),matrix_bit=dict(row2_outputs=column,updates=variation['updates'],queries=variation['queries']),insert_only_wrong=stale_rows,parity_wrong=parity,transpose_wrong=transpose,lookahead=dict(error=blocked,provider_calls=invoked,events=p.events))

def main():
    edges=[(10,0,1,4),(11,0,1,7),(20,1,2,-2),(30,0,2,8),(40,2,3,3),(50,1,3,6),(60,3,1,0)]
    z=Closure(5,edges);check(z.d[0][3]==5,'main distance');main_closure=z.summary();main_closure['route_0_3']=z.walk(0,3)
    bad=Closure(5,edges+[(70,3,1,-2)]).summary();check(bad['status']=='NEGATIVE_CYCLE','negative migration')
    a=[[0,4,None],[-1,2,5],[None,0,3]];b=[[3,None,1],[2,-2,None],[None,4,0]];c,k,t=product(a,b);layer,graph=product_via_apsp(a,b);check(c==layer,'main product')
    m=[[1,0,1,0],[0,1,1,0],[0,0,0,0],[1,0,0,1]];vectors=[[1,0,1,0],[0,1,0,1],[0,0,0,0],[1,1,1,1]]
    direct=online(m,Protocol(m,lambda t,last:vectors[t]));blocked=online(m,Protocol(m,lambda t,last:vectors[t]),2)
    result=dict(status='PASS',closure=main_closure,negative_migration=bad,product=dict(a=a,b=b,c=c,argmin=k,candidate_tests=t,graph=graph),matrix=m,vectors=vectors,direct=direct,blocked=blocked,budget_c5_epsilon_third=budget(5,'1/3'),migrations=migrations(m,vectors),self_checks=tests())
    print(json.dumps(result,ensure_ascii=False,indent=2))
if __name__=='__main__':main()