import json,math,pathlib,subprocess,time,resource from common1133 import read,ROOT,RED_SHA,BASIS_SHA start=time.process_time();child0=resource.getrusage(resource.RUSAGE_CHILDREN) gate=json.loads((ROOT/'price-receipt1133.json').read_text());assert gate['gate']=='pass' p=gate['attempts'][-1]['prime'];ordering=json.loads((ROOT/'ordering1133.json').read_text());pr=ordering['row'];pc=ordering['column'] C,B,F,e,b=read();n=len(B) def recon(a,m,bound): if a==0:return (0,1) r0,r1,t0,t1=m,a,0,1 while abs(r1)>bound: q=r0//r1;r0,r1=r1,r0-q*r1;t0,t1=t1,t0-q*t1 if t1==0 or abs(t1)>bound or math.gcd(r1,t1)!=1 or math.gcd(t1,m)!=1:return None if (a*t1-r1)%m:return None return (r1,t1) if t1>0 else (-r1,-t1) def elapsed(): c=resource.getrusage(resource.RUSAGE_CHILDREN);return time.process_time()-start+c.ru_utime+c.ru_stime-child0.ru_utime-child0.ru_stime proc=subprocess.Popen([str(ROOT/'sparse1133'),'solve',str(ROOT/'factor1133.txt')],stdin=subprocess.PIPE,stdout=subprocess.PIPE,stderr=subprocess.PIPE,text=True,bufsize=1) x=[0]*n;d=b[:];modulus=1;stages=[];verdict='no_exact_candidate';candidate=None try: for k in range(1,91): if elapsed()>890:verdict='cpu_cap';break rhs=[0]*n for i,v in enumerate(d):rhs[pr[i]]=v%p proc.stdin.write(' '.join(map(str,rhs))+'\n');proc.stdin.flush() line=proc.stdout.readline();z=list(map(int,line.split()));assert len(z)==n y=[z[pc[j]] for j in range(n)] # This exact divisibility check both validates each modular solve and supplies # Dixon's next integer residual. All arithmetic here is Python big integers. resid=d[:] for i,j,v in e:resid[i]-=v*y[j] assert all(v%p==0 for v in resid),'modular residual failed' d=[v//p for v in resid] x=[a+v*modulus for a,v in zip(x,y)];modulus*=p if k not in [16,32,64,90]:continue bound=math.isqrt((modulus-1)//2);assert 2*bound*bound