# Add internal numeric base (4)
# @see kuVRVb
 
import itertools
import operator
 
class Num:
    base = 2**8
 
    def __init__(self, init=0):
        if isinstance(init, tuple):
            self.m = init[0].copy()
            self.s = init[1]
        else:
            self.m = iton(abs(init), Num.base)
            self.s = init < 0
 
    def __neg__(self):
        return Num((self.m, not self.s))
 
    def __add__(self, other):
        return Num(nadd(self.m, self.s, other.m, other.s, Num.base))
 
    def __sub__(self, other):
        return Num(nadd(self.m, self.s, other.m, not other.s, Num.base))
 
    def __mul__(self, other):
        return Num(nmul(self.m, self.s, other.m, other.s, Num.base))
 
    def __str__(self):
        return '-' * self.s + ntos(self.m, Num.base)
 
    def __repr__(self):
        return str((self.m, self.s))
 
# Utility.
 
def _fixsign(a, s):
    return a, False if _iszero(a) else s
 
def _iszero(a):
    return len(a) == 1 and a[0] == 0
 
def _zeroextend(a, n):
    return a[:] + [0] * (n - len(a))
 
def _zeroreduce(a):
    n = len(a)
    while n != 1 and a[n-1] == 0:
        n -= 1
    return a[:n]
 
# Convert.
 
def iton(x, b):
    r = []
    while True:
        x, y = divmod(x, b)
        r.append(y)
        if x == 0:
            return r
 
def nton(a, bi, bo):
    r = [0]
    for x in reversed(a):
        for i in range(len(r)):
            x, r[i] = divmod(r[i] * bi + x, bo)
        if x != 0:
            r.extend(iton(x, bo))
    return r
 
def ntos(a, b):
    return ''.join(map(str, reversed(nton(a, b, 10))))
 
# Compare.
 
def _cmp(x, y):
    if x != y:
        return -1 if x < y else 1
    return 0
 
def ncmp(a, b):
    n = len(a)
    m = len(b)
    u = itertools.chain([n], reversed(a))
    v = itertools.chain([m], reversed(b))
    return next(itertools.dropwhile(lambda x: x == 0, map(_cmp, u, v)), 0)
 
# Shift.
 
def nshl(a, n):
    return _zeroreduce([0] * n + a[:])
 
def nshr(a, n):
    return _zeroextend(a[n:], 1)
 
# Add.
 
def _add(a, b, base, op):
    n = 1 + max(len(a), len(b))
    r = _zeroextend(a, n)
    b = _zeroextend(b, n)
    c = 0
    for i in range(n):
        c, r[i] = divmod(op(r[i], b[i] + abs(c)), base)
    return _zeroreduce(r)
 
def nadd(a, s, b, t, base):
    if s == t:
        return _fixsign(_add(a, b, base, operator.add), s)
    elif ncmp(a, b) < 0:
        return _fixsign(_add(b, a, base, operator.sub), t)
    else:
        return _fixsign(_add(a, b, base, operator.sub), s)
 
# Multiply.
 
def _mul1(a, x, base):
    n = 1 + len(a)
    r = _zeroextend(a, n)
    c = 0
    for i in range(n):
        c, r[i] = divmod(r[i] * x + c, base)
    return _zeroreduce(r)
 
def _mul(a, b, base):
    if _iszero(b):
        return [0]
    return _add(_mul1(a, b[0], base), _mul(nshl(a, 1), nshr(b, 1), base),
                base, operator.add)
 
def nmul(a, s, b, t, base):
    return _fixsign(_mul(a, b, base), s != t)
 
# Test.
 
def _test(n, op):
    for x, y in itertools.product(range(-n, n+1), repeat=2):
        u = int(str(op(Num(x), Num(y))))
        v = op(x, y)
        assert u == v, f'{op}({x}, {y})\nExpected:{v}, Got:{u}'
 
n = 50
_test(n, operator.add)
_test(n, operator.sub)
_test(n, operator.mul)
 
def factorial(n):
    r = Num(1)
    for i in range(2, n+1):
        r *= Num(i)
    return r
 
def show(a):
    print(repr(a), a, sep='; ')
 
x = 12345
z = (0, 1, -1, x, -x)
for x in z:
    show(Num(x))
print('+')
for x, y in itertools.product(z, repeat=2):
    show(Num(x) + Num(y))
print('-')
for x, y in itertools.product(z, repeat=2):
    show(Num(x) - Num(y))
print('*')
for x, y in itertools.product(z, repeat=2):
    show(Num(x) * Num(y))
print('f')
for i in range(5):
    show(factorial(10*i))

IyBBZGQgaW50ZXJuYWwgbnVtZXJpYyBiYXNlICg0KQojIEBzZWUga3VWUlZiCgppbXBvcnQgaXRlcnRvb2xzCmltcG9ydCBvcGVyYXRvcgoKY2xhc3MgTnVtOgogICAgYmFzZSA9IDIqKjgKCiAgICBkZWYgX19pbml0X18oc2VsZiwgaW5pdD0wKToKICAgICAgICBpZiBpc2luc3RhbmNlKGluaXQsIHR1cGxlKToKICAgICAgICAgICAgc2VsZi5tID0gaW5pdFswXS5jb3B5KCkKICAgICAgICAgICAgc2VsZi5zID0gaW5pdFsxXQogICAgICAgIGVsc2U6CiAgICAgICAgICAgIHNlbGYubSA9IGl0b24oYWJzKGluaXQpLCBOdW0uYmFzZSkKICAgICAgICAgICAgc2VsZi5zID0gaW5pdCA8IDAKCiAgICBkZWYgX19uZWdfXyhzZWxmKToKICAgICAgICByZXR1cm4gTnVtKChzZWxmLm0sIG5vdCBzZWxmLnMpKQoKICAgIGRlZiBfX2FkZF9fKHNlbGYsIG90aGVyKToKICAgICAgICByZXR1cm4gTnVtKG5hZGQoc2VsZi5tLCBzZWxmLnMsIG90aGVyLm0sIG90aGVyLnMsIE51bS5iYXNlKSkKCiAgICBkZWYgX19zdWJfXyhzZWxmLCBvdGhlcik6CiAgICAgICAgcmV0dXJuIE51bShuYWRkKHNlbGYubSwgc2VsZi5zLCBvdGhlci5tLCBub3Qgb3RoZXIucywgTnVtLmJhc2UpKQoKICAgIGRlZiBfX211bF9fKHNlbGYsIG90aGVyKToKICAgICAgICByZXR1cm4gTnVtKG5tdWwoc2VsZi5tLCBzZWxmLnMsIG90aGVyLm0sIG90aGVyLnMsIE51bS5iYXNlKSkKCiAgICBkZWYgX19zdHJfXyhzZWxmKToKICAgICAgICByZXR1cm4gJy0nICogc2VsZi5zICsgbnRvcyhzZWxmLm0sIE51bS5iYXNlKQoKICAgIGRlZiBfX3JlcHJfXyhzZWxmKToKICAgICAgICByZXR1cm4gc3RyKChzZWxmLm0sIHNlbGYucykpCgojIFV0aWxpdHkuCgpkZWYgX2ZpeHNpZ24oYSwgcyk6CiAgICByZXR1cm4gYSwgRmFsc2UgaWYgX2lzemVybyhhKSBlbHNlIHMKCmRlZiBfaXN6ZXJvKGEpOgogICAgcmV0dXJuIGxlbihhKSA9PSAxIGFuZCBhWzBdID09IDAKCmRlZiBfemVyb2V4dGVuZChhLCBuKToKICAgIHJldHVybiBhWzpdICsgWzBdICogKG4gLSBsZW4oYSkpCgpkZWYgX3plcm9yZWR1Y2UoYSk6CiAgICBuID0gbGVuKGEpCiAgICB3aGlsZSBuICE9IDEgYW5kIGFbbi0xXSA9PSAwOgogICAgICAgIG4gLT0gMQogICAgcmV0dXJuIGFbOm5dCgojIENvbnZlcnQuCgpkZWYgaXRvbih4LCBiKToKICAgIHIgPSBbXQogICAgd2hpbGUgVHJ1ZToKICAgICAgICB4LCB5ID0gZGl2bW9kKHgsIGIpCiAgICAgICAgci5hcHBlbmQoeSkKICAgICAgICBpZiB4ID09IDA6CiAgICAgICAgICAgIHJldHVybiByCgpkZWYgbnRvbihhLCBiaSwgYm8pOgogICAgciA9IFswXQogICAgZm9yIHggaW4gcmV2ZXJzZWQoYSk6CiAgICAgICAgZm9yIGkgaW4gcmFuZ2UobGVuKHIpKToKICAgICAgICAgICAgeCwgcltpXSA9IGRpdm1vZChyW2ldICogYmkgKyB4LCBibykKICAgICAgICBpZiB4ICE9IDA6CiAgICAgICAgICAgIHIuZXh0ZW5kKGl0b24oeCwgYm8pKQogICAgcmV0dXJuIHIKCmRlZiBudG9zKGEsIGIpOgogICAgcmV0dXJuICcnLmpvaW4obWFwKHN0ciwgcmV2ZXJzZWQobnRvbihhLCBiLCAxMCkpKSkKCiMgQ29tcGFyZS4KCmRlZiBfY21wKHgsIHkpOgogICAgaWYgeCAhPSB5OgogICAgICAgIHJldHVybiAtMSBpZiB4IDwgeSBlbHNlIDEKICAgIHJldHVybiAwCgpkZWYgbmNtcChhLCBiKToKICAgIG4gPSBsZW4oYSkKICAgIG0gPSBsZW4oYikKICAgIHUgPSBpdGVydG9vbHMuY2hhaW4oW25dLCByZXZlcnNlZChhKSkKICAgIHYgPSBpdGVydG9vbHMuY2hhaW4oW21dLCByZXZlcnNlZChiKSkKICAgIHJldHVybiBuZXh0KGl0ZXJ0b29scy5kcm9wd2hpbGUobGFtYmRhIHg6IHggPT0gMCwgbWFwKF9jbXAsIHUsIHYpKSwgMCkKCiMgU2hpZnQuCgpkZWYgbnNobChhLCBuKToKICAgIHJldHVybiBfemVyb3JlZHVjZShbMF0gKiBuICsgYVs6XSkKCmRlZiBuc2hyKGEsIG4pOgogICAgcmV0dXJuIF96ZXJvZXh0ZW5kKGFbbjpdLCAxKQoKIyBBZGQuCgpkZWYgX2FkZChhLCBiLCBiYXNlLCBvcCk6CiAgICBuID0gMSArIG1heChsZW4oYSksIGxlbihiKSkKICAgIHIgPSBfemVyb2V4dGVuZChhLCBuKQogICAgYiA9IF96ZXJvZXh0ZW5kKGIsIG4pCiAgICBjID0gMAogICAgZm9yIGkgaW4gcmFuZ2Uobik6CiAgICAgICAgYywgcltpXSA9IGRpdm1vZChvcChyW2ldLCBiW2ldICsgYWJzKGMpKSwgYmFzZSkKICAgIHJldHVybiBfemVyb3JlZHVjZShyKQoKZGVmIG5hZGQoYSwgcywgYiwgdCwgYmFzZSk6CiAgICBpZiBzID09IHQ6CiAgICAgICAgcmV0dXJuIF9maXhzaWduKF9hZGQoYSwgYiwgYmFzZSwgb3BlcmF0b3IuYWRkKSwgcykKICAgIGVsaWYgbmNtcChhLCBiKSA8IDA6CiAgICAgICAgcmV0dXJuIF9maXhzaWduKF9hZGQoYiwgYSwgYmFzZSwgb3BlcmF0b3Iuc3ViKSwgdCkKICAgIGVsc2U6CiAgICAgICAgcmV0dXJuIF9maXhzaWduKF9hZGQoYSwgYiwgYmFzZSwgb3BlcmF0b3Iuc3ViKSwgcykKCiMgTXVsdGlwbHkuCgpkZWYgX211bDEoYSwgeCwgYmFzZSk6CiAgICBuID0gMSArIGxlbihhKQogICAgciA9IF96ZXJvZXh0ZW5kKGEsIG4pCiAgICBjID0gMAogICAgZm9yIGkgaW4gcmFuZ2Uobik6CiAgICAgICAgYywgcltpXSA9IGRpdm1vZChyW2ldICogeCArIGMsIGJhc2UpCiAgICByZXR1cm4gX3plcm9yZWR1Y2UocikKCmRlZiBfbXVsKGEsIGIsIGJhc2UpOgogICAgaWYgX2lzemVybyhiKToKICAgICAgICByZXR1cm4gWzBdCiAgICByZXR1cm4gX2FkZChfbXVsMShhLCBiWzBdLCBiYXNlKSwgX211bChuc2hsKGEsIDEpLCBuc2hyKGIsIDEpLCBiYXNlKSwKICAgICAgICAgICAgICAgIGJhc2UsIG9wZXJhdG9yLmFkZCkKCmRlZiBubXVsKGEsIHMsIGIsIHQsIGJhc2UpOgogICAgcmV0dXJuIF9maXhzaWduKF9tdWwoYSwgYiwgYmFzZSksIHMgIT0gdCkKCiMgVGVzdC4KCmRlZiBfdGVzdChuLCBvcCk6CiAgICBmb3IgeCwgeSBpbiBpdGVydG9vbHMucHJvZHVjdChyYW5nZSgtbiwgbisxKSwgcmVwZWF0PTIpOgogICAgICAgIHUgPSBpbnQoc3RyKG9wKE51bSh4KSwgTnVtKHkpKSkpCiAgICAgICAgdiA9IG9wKHgsIHkpCiAgICAgICAgYXNzZXJ0IHUgPT0gdiwgZid7b3B9KHt4fSwge3l9KVxuRXhwZWN0ZWQ6e3Z9LCBHb3Q6e3V9JwoKbiA9IDUwCl90ZXN0KG4sIG9wZXJhdG9yLmFkZCkKX3Rlc3Qobiwgb3BlcmF0b3Iuc3ViKQpfdGVzdChuLCBvcGVyYXRvci5tdWwpCgpkZWYgZmFjdG9yaWFsKG4pOgogICAgciA9IE51bSgxKQogICAgZm9yIGkgaW4gcmFuZ2UoMiwgbisxKToKICAgICAgICByICo9IE51bShpKQogICAgcmV0dXJuIHIKCmRlZiBzaG93KGEpOgogICAgcHJpbnQocmVwcihhKSwgYSwgc2VwPSc7ICcpCgp4ID0gMTIzNDUKeiA9ICgwLCAxLCAtMSwgeCwgLXgpCmZvciB4IGluIHo6CiAgICBzaG93KE51bSh4KSkKcHJpbnQoJysnKQpmb3IgeCwgeSBpbiBpdGVydG9vbHMucHJvZHVjdCh6LCByZXBlYXQ9Mik6CiAgICBzaG93KE51bSh4KSArIE51bSh5KSkKcHJpbnQoJy0nKQpmb3IgeCwgeSBpbiBpdGVydG9vbHMucHJvZHVjdCh6LCByZXBlYXQ9Mik6CiAgICBzaG93KE51bSh4KSAtIE51bSh5KSkKcHJpbnQoJyonKQpmb3IgeCwgeSBpbiBpdGVydG9vbHMucHJvZHVjdCh6LCByZXBlYXQ9Mik6CiAgICBzaG93KE51bSh4KSAqIE51bSh5KSkKcHJpbnQoJ2YnKQpmb3IgaSBpbiByYW5nZSg1KToKICAgIHNob3coZmFjdG9yaWFsKDEwKmkpKQ==