"""Minimal Grassmann algebra with sympy coefficients, and supermatrices."""
import sympy as sp

def _mul_mono(a, b):
    # a, b sorted tuples of generator indices; return (sign, merged) or (0, None)
    if set(a) & set(b):
        return 0, None
    inv = 0
    for x in a:
        for y in b:
            if x > y:
                inv += 1
    return (-1) ** inv, tuple(sorted(a + b))

class G:
    __slots__ = ("d",)
    def __init__(self, d=None):
        self.d = {}
        if d:
            for k, v in d.items():
                if v != 0:
                    self.d[k] = v
    @staticmethod
    def c(x):
        return G({(): sp.sympify(x)})
    @staticmethod
    def gen(i):
        return G({(i,): sp.Integer(1)})
    def copy(self):
        return G(dict(self.d))
    def __add__(self, o):
        o = o if isinstance(o, G) else G.c(o)
        d = dict(self.d)
        for k, v in o.d.items():
            d[k] = d.get(k, 0) + v
        return G(d)
    __radd__ = __add__
    def __neg__(self):
        return G({k: -v for k, v in self.d.items()})
    def __sub__(self, o):
        o = o if isinstance(o, G) else G.c(o)
        return self + (-o)
    def __rsub__(self, o):
        return G.c(o) - self
    def __mul__(self, o):
        if not isinstance(o, G):
            o = sp.sympify(o)
            return G({k: v * o for k, v in self.d.items()})
        d = {}
        for ka, va in self.d.items():
            for kb, vb in o.d.items():
                s, m = _mul_mono(ka, kb)
                if s:
                    d[m] = d.get(m, 0) + s * va * vb
        return G(d)
    def __rmul__(self, o):
        o = sp.sympify(o)
        return G({k: o * v for k, v in self.d.items()})
    def body(self):
        return self.d.get((), sp.Integer(0))
    def coeff(self, mono):
        return self.d.get(tuple(sorted(mono)), sp.Integer(0))
    def dleft(self, i):
        """left derivative d/d xi_i"""
        d = {}
        for k, v in self.d.items():
            if i in k:
                r = k.index(i)
                m = k[:r] + k[r + 1:]
                d[m] = d.get(m, 0) + (-1) ** r * v
        return G(d)
    def diff(self, x):
        return G({k: sp.diff(v, x) for k, v in self.d.items()})
    def applyc(self, fn):
        return G({k: fn(v) for k, v in self.d.items()})
    def subs(self, s):
        return G({k: v.subs(s) for k, v in self.d.items()})
    def parity_ok(self, p):
        return all(len(k) % 2 == p for k in self.d)
    def __repr__(self):
        return " + ".join(f"({v})*xi{list(k)}" for k, v in self.d.items()) or "0"

def mzero(n, m=None):
    m = n if m is None else m
    return [[G() for _ in range(m)] for _ in range(n)]

def meye(n):
    M = mzero(n)
    for i in range(n):
        M[i][i] = G.c(1)
    return M

def mmul(A, B):
    n, k, m = len(A), len(B), len(B[0])
    C = mzero(n, m)
    for i in range(n):
        for j in range(m):
            s = G()
            for l in range(k):
                if A[i][l].d and B[l][j].d:
                    s = s + A[i][l] * B[l][j]
            C[i][j] = s
    return C

def madd(A, B):
    return [[A[i][j] + B[i][j] for j in range(len(A[0]))] for i in range(len(A))]

def msub(A, B):
    return [[A[i][j] - B[i][j] for j in range(len(A[0]))] for i in range(len(A))]

def mscale(c, A):
    return [[A[i][j] * c for j in range(len(A[0]))] for i in range(len(A))]

def mapply(A, fn):
    return [[fn(A[i][j]) for j in range(len(A[0]))] for i in range(len(A))]