"""Proposition 22.1, steps 2-4: among all Weyl elements, the ones for which the descent character
can be trivial on U_desc ∩ w^{-1}Qw form exactly one double coset W_Q w0 W_M, w0 as in the text,
and U_desc ∩ w0^{-1} Q w0 is the product of the root groups e_i+e_{r+k}, k<=i.
Weights: eps_1..eps_m. A Weyl element is (perm, signs): eps_i -> signs[i]*eps_{perm[i]}."""
import itertools,sys
def roots(m,typ):
    R=[]
    for i in range(m):
        for j in range(i+1,m):
            for a in (1,-1):
                for b in (1,-1):
                    v=[0]*m; v[i]=a; v[j]=b; R.append(tuple(v))
    if typ=='B':
        for i in range(m):
            for a in (1,-1):
                v=[0]*m; v[i]=a; R.append(tuple(v))
    return R
def positive(v):
    for x in v:
        if x: return x>0
def act(w,v):
    perm,sg=w; out=[0]*len(v)
    for i,x in enumerate(v):
        if x: out[perm[i]]=sg[i]*x
    return tuple(out)
def run(typ,r,variant='+',char2=False):
    m=2*r+2 if typ=='D' else 2*r
    n=m//2
    R=roots(m,typ)
    # Levi roots of Q
    lev=set()
    for j in range(n):
        v=[0]*m; v[2*j]=1; v[2*j+1]=-1
        if typ=='D' and variant=='-' and j==n-1: v[2*j+1]=1
        lev.add(tuple(v)); lev.add(tuple(-x for x in v))
    def posQ(v):
        # positive system adapted to Q_-: flip sign of last coordinate
        if typ=='D' and variant=='-':
            v=v[:-1]+(-v[-1],)
        return positive(v)
    PhiQ=set(v for v in R if v in lev or posQ(v))
    U=[v for v in R if positive(v) and any(v[i] for i in range(r))]
    simple=[]
    for i in range(r-1):
        v=[0]*m; v[i]=1; v[i+1]=-1; simple.append(tuple(v))
    def ok(w):
        Pw=[a for a in U if act(w,a) in PhiQ]
        S=set(Pw)
        if any(s in S for s in simple): return False,Pw
        # last row constraints
        free_pair=False
        for h in range(r,m):
            a=[0]*m; a[r-1]=1; a[h]=-1; b=[0]*m; b[r-1]=1; b[h]=1
            if tuple(a) not in S and tuple(b) not in S: free_pair=True
        if typ=='D': return free_pair,Pw
        short=[0]*m; short[r-1]=1; short=tuple(short)
        if char2: return (short not in S),Pw
        return (free_pair or short not in S),Pw
    good=[]
    for perm in itertools.permutations(range(m)):
        for sg in itertools.product((1,-1),repeat=m):
            if typ=='D' and sg.count(-1)%2: continue
            w=(perm,sg)
            g,_=ok(w)
            if g: good.append(w)
    # the element of the text
    perm=[None]*m; sg=[1]*m
    for i in range(1,r+1):
        perm[i-1]=2*i-2; sg[i-1]=-1          # e_i -> f_{2i-1}
        perm[r+i-1]=2*i-1                    # e_{r+i} -> e_{2i}
    if typ=='D':
        perm[m-2]=m-2; perm[m-1]=m-1
        flip=(r%2==1)
        # for Q_- = sigma Q_+ sigma^{-1} the representative sigma w0 sigma^{-1} is the same signed permutation
        if flip: sg[m-1]=-1
    w0=(tuple(perm),tuple(sg))
    # double coset W_Q w0 W_M
    def mul(a,b):  # a∘b
        pa,sa=a; pb,sb=b
        return (tuple(pa[pb[i]] for i in range(m)),tuple(sb[i]*sa[pb[i]] for i in range(m)))
    WQ=[]
    for bits in itertools.product((0,1),repeat=n):
        perm=list(range(m)); sg=[1]*m
        for j,bt in enumerate(bits):
            if bt:
                perm[2*j],perm[2*j+1]=2*j+1,2*j
                if typ=='D' and variant=='-' and j==n-1: sg[2*j]=sg[2*j+1]=-1
        WQ.append((tuple(perm),tuple(sg)))
    WM=[]
    rest=list(range(r,m))
    for p in itertools.permutations(rest):
        for sgs in itertools.product((1,-1),repeat=m-r):
            if typ=='D' and sgs.count(-1)%2: continue
            WM.append((tuple(list(range(r))+list(p)),tuple([1]*r+list(sgs))))
    coset=set(mul(mul(a,w0),b) for a in WQ for b in WM)
    g0,P0=ok(w0)
    expect=set()
    for k in range(1,r+1):
        for i in range(k,r+1):
            v=[0]*m; v[i-1]=1; v[r+k-1]=1; expect.add(tuple(v))
    print(f"type {typ}{m} r={r} Q_{variant} char2={char2}: good={len(good)} coset={len(coset)} "
          f"equal={set(good)==coset} w0 good={g0} U_int as stated={set(P0)==expect}")
run('B',1); run('B',2); run('B',3)
run('B',1,char2=True); run('B',2,char2=True); run('B',3,char2=True)
run('D',1,'+'); run('D',1,'-'); run('D',2,'+'); run('D',2,'-')