# KL basis in affine type A~_{n-1} Hecke algebra (Soergel normalization):
# (H_s + v)(H_s - v^{-1}) = 0, C_s = H_s + v.
# Elements of W_aff = affine permutations (window notation), sum f(i) = sum i.
import sys, itertools
from functools import lru_cache
n = int(sys.argv[1]); L = int(sys.argv[2])

def rmul_s(f, i):  # f * s_i : swap positions i, i+1 (i in 0..n-1)
    f = list(f)
    if i == 0:
        # positions 0 and 1: f(0)=f(n)-n
        a = f[n-1] - n; b = f[0]
        f[0] = a; f[n-1] = b + n
    else:
        f[i-1], f[i] = f[i], f[i-1]
    return tuple(f)
def lmul_s(f, i):  # s_i * f : swap values congruent to i, i+1
    g = []
    for x in f:
        r = x % n
        if r == i % n: g.append(x+1)
        elif r == (i+1) % n: g.append(x-1)
        else: g.append(x)
    return tuple(g)
def length(f):
    l = 0
    for i in range(n):
        for j in range(i+1, n):
            d = f[j]-f[i]
            # count k in Z with i<j+kn and f(i)>f(j)+kn
            # pairs (i, j+kn), k>=0 : f(i) > f(j)+kn ; pairs (j, i+kn), k>=1: f(j) > f(i)+kn
            # standard formula: |floor((f(j)-f(i))/n)|
            l += abs((f[j]-f[i]) // n)
    return l
def val(f, i):  # f(i) for any integer i
    q, r = divmod(i-1, n)
    return f[r] + q*n
def rdes(f, i):  # f s_i < f  iff f(i) > f(i+1)
    return val(f, i) > val(f, i+1)
e = tuple(range(1, n+1))
# Laurent polys as dicts
def padd(p, q, c=1):
    r = dict(p)
    for k, v in q.items():
        r[k] = r.get(k, 0) + c*v
        if r[k] == 0: del r[k]
    return r
def pmul(p, q):
    r = {}
    for a, x in p.items():
        for b, y in q.items():
            r[a+b] = r.get(a+b, 0) + x*y
    return {k: v for k, v in r.items() if v}
def hadd(A, B, c=None):
    R = dict(A)
    for w, p in B.items():
        pp = pmul(p, c) if c is not None else p
        R[w] = padd(R.get(w, {}), pp)
        if not R[w]: del R[w]
    return R
def times_Hs(A, i):  # A * H_s
    R = {}
    for w, p in A.items():
        ws = rmul_s(w, i)
        if not rdes(w, i):
            R = hadd(R, {ws: p})
        else:
            R = hadd(R, {ws: p})
            R = hadd(R, {w: pmul(p, {-1: 1, 1: -1})})
    return R
def times_Cs(A, i):
    return hadd(times_Hs(A, i), A, {1: 1})
def s_times(i, A):  # H_s * A via left mult
    R = {}
    for w, p in A.items():
        sw = lmul_s(w, i)
        if length(sw) > length(w):
            R = hadd(R, {sw: p})
        else:
            R = hadd(R, {sw: p})
            R = hadd(R, {w: pmul(p, {-1: 1, 1: -1})})
    return R
Ccache = {e: {e: {0: 1}}}
def C(w):
    if w in Ccache: return Ccache[w]
    for i in range(n):
        if rdes(w, i):
            wp = rmul_s(w, i); break
    A = times_Cs(C(wp), i)
    # subtract mu(z,wp) C_z for z<wp, zs<z
    for z, p in list(C(wp).items()):
        if z != wp and rdes(z, i):
            mu = p.get(1, 0)
            if mu:
                A = hadd(A, C(z), {0: -mu})
    Ccache[w] = A
    return A
def mult(A, B):  # A * B, B expanded via C's: use B in H basis; H_w = product of H_s
    R = {}
    for w, p in B.items():
        # A * H_w: reduced word of w
        word = []
        x = w
        while x != e:
            for i in range(n):
                if rdes(x, i):
                    word.append(i); x = rmul_s(x, i); break
        T = A
        for i in reversed(word):
            T = times_Hs(T, i)
        R = hadd(R, T, p)
    return R
def toC(A):
    A = dict(A); res = {}
    while A:
        z = max(A, key=length)
        c = A[z]
        res[z] = c
        A = hadd(A, C(z), {k: -v for k, v in c.items()})
    return res
# enumerate elements up to length L
elems = {e}; frontier = {e}
for _ in range(L):
    new = set()
    for f in frontier:
        for i in range(n):
            g = rmul_s(f, i)
            if length(g) == length(f)+1: new.add(g)
    elems |= new; frontier = new
# w0 of finite W (generated by s_1..s_{n-1})
w0 = tuple(range(n, 0, -1))
print("n =", n, " #elements up to length", L, "=", len(elems), " l(w0) =", length(w0))
# longest elements w_J for J = S minus one node (all have l = l(w0) in type A~)
def longest_parabolic(J):
    best = e; frontier = {e}; seen = {e}
    while frontier:
        new = set()
        for f in frontier:
            for i in J:
                g = rmul_s(f, i)
                if length(g) == length(f)+1 and g not in seen:
                    new.add(g); seen.add(g)
        if new: best = max(new, key=length)
        frontier = new
    return best
wJs = [longest_parabolic([j for j in range(n) if j != k]) for k in range(n)]
nu = length(w0)
# c0 up to large length: x wJ y reduced
big = set(elems)
frontier = set(elems)
Lbig = 2*L + nu
allel = {e}; fr = {e}
for _ in range(Lbig):
    new = set()
    for f in fr:
        for i in range(n):
            g = rmul_s(f, i)
            if length(g) == length(f)+1: new.add(g)
    allel |= new; fr = new
def compose(f, g):  # (f g)(i) = f(g(i))
    return tuple(val(f, g[i]) for i in range(n))
c0 = set()
for wJ in wJs:
    for x in allel:
        for y in allel:
            if length(x)+nu+length(y) <= Lbig:
                z = compose(compose(x, wJ), y)
                if length(z) == length(x)+nu+length(y): c0.add(z)
print("c0 elements with length <=", Lbig, ":", len(c0))
appear = set(); negative = False
for x in elems:
    for y in elems:
        P = mult(mult(C(x), C(w0)), C(y))
        D = toC(P)
        for z, p in D.items():
            if any(v < 0 for v in p.values()): negative = True
            appear.add(z)
print("any negative coefficient:", negative)
print("#z appearing:", len(appear), " all in c0:", appear <= c0)
print("identity appears:", e in appear)
simples = [rmul_s(e, i) for i in range(n)]
print("simple reflections appearing:", [s for s in simples if s in appear])
short = sorted([z for z in appear if length(z) <= nu+1], key=length)
print("appearing z of length <= nu+1:", [(z, length(z)) for z in short])
c0small = {z for z in c0 if length(z) <= nu + 2}
print("c0 of length<=nu+2 covered:", c0small <= appear, len(c0small), len(c0small & appear))