BigInt = {}
BigInt.__index = BigInt


local function trim(a)
    for i = #a, 2, -1 do
        if a[i] ~= 0 then break end
        table.remove(a)
    end
    if #a == 1 and a[1] == 0 then a.sign = 1 end
end

local function num2tab(n)
    local t = {sign=1}
    local i = 1
    if n < 0 then
        n = -n
        t.sign = -1
    end
    repeat
        local r = math.fmod(n, 10)
        n = math.floor(n / 10)
        t[i] = r
        i = i + 1
    until n == 0
    return t
end

local function str2tab(s)
    local s = s:gsub("[ ,]", ""):match("^[+-]?%d+$") or "0"
    local t = {sign=1}
    local i = #s
    local j = 1
    local first = 1
    if s:sub(1, 1) == '-' then t.sign=-1;first=2 end
    if s:sub(1, 1) == '+' then first=2 end
    while i >= first do
        t[j] = s:sub(i, i):byte()-48
        j = j + 1
        i = i - 1
    end
    return t
end

local function iterZip(a, b)
    local a = BigInt(a)
    local b = BigInt(b)
    local i = 1
    return function()
        if not a[i] and not b[i] then return end
        local ai = a[i] or 0
        local bi = b[i] or 0
        i = i + 1
        return ai, bi, i-1
    end
end

local function iterZipRev(a, b, n)
    local a = BigInt(a)
    local b = BigInt(b)
    local i = n
    if not i then
        i = #a
        if #b > i then i = #b end
    end
    return function()
        if i<1 then return end
        local ai = a[i] or 0
        local bi = b[i] or 0
        i = i - 1
        return ai, bi, i+1
    end
end

local function concat(a, b)
    if not b then return a:clone() end
    local c = b:clone()
    local n = #c
    for i in ipairs(a) do
        n = n + 1
        c[n] = a[i]
    end
    c.sign = a.sign
    trim(c)
    return c
end

local function append(a, d)
    table.insert(a, 1, d)
    trim(a)
end

local function uadd(a, b)
    local c = BigInt()
    local carry = 0
    for ai, bi, i in iterZip(a, b) do
        local ci = ai + bi + carry
        if ci > 9 then
            ci = ci - 10
            carry = 1
        else
            carry = 0
        end
        c[i] = ci
    end
    trim(c)
    return c
end

local function ult(a, b)
    for ai, bi in iterZipRev(a, b) do
        if ai < bi then return true end
        if bi < ai then return false end
    end
    return false
end

local function usub(a, b)
    local c = BigInt()
    if ult(a, b) then a, b = b, a; c.sign = -1 end
    local borrow = 0
    local ci
    for ai, bi, i in iterZip(a, b) do
        ci = (ai - borrow) - bi
        if ci < 0 then
            -- ci = 10 + ai - borrow - bi
            ci = ci + 10
            borrow = 1
        else
            borrow = 0
        end
        c[i] = ci
    end
    trim(c)
    return c
end

local function udiv(a, b)
    local a = BigInt(a):clone()
    local b = BigInt(b):clone()
    local q = BigInt()
    local d = BigInt()
    local r
    a.sign = 1
    b.sign = 1
    if b == q then return end
    if a == q then return q, q end
    -- if a < b then return q, a:clone() end
    if a < b then return q, a end
    if a == b then return BigInt(1), q end
    -- if #b == 1 and b[1] == 1 then return a:clone(), q end
    if #b == 1 and b[1] == 1 then return a, q end
    for k = #a, 1, -1 do
        -- d:append(a[k])
        append(d, a[k])
        if d >= b then
            for i = 10, 1, -1 do
                r = d - i * b
                if r.sign == 1 then 
                    -- q = q:concat(BigInt(i))
                    q = concat(q, BigInt(i))
                    break
                end
            end
            d = r
        else
            q = q * 10
        end
    end
    return q, r
end

local function uinc(a)
    -- in place
    local i = 1
    local c = 1
    repeat
        if not a[i] then a[i] = 0 end
        a[i] = a[i] + c
        c = 0
        if a[i] > 9 then
            a[i] = a[i] - 10
            c = 1
        end
        i = i + 1
    until c == 0
end

local function udec(a)
    -- in place
    if #a == 1 and a[1] == 0 then
        a[1] = 1
        a.sign = -1
        return
    end
    local i = 1
    local c = 1
    repeat
        a[i] = a[i] - c
        c = 0
        if a[i] < 0 then
            a[i] = a[i] + 10
            c = 1
        end
        i = i + 1
    until c == 0
    trim(a)
end

local function upow(a, b)
    -- https://stackoverflow.com/a/102319/2332397
    if #b == 1 and b[1] == 0 then return BigInt(1) end
    local temp = upow(a, b/2)
    if b[1] % 2 == 0 then
        return temp * temp
    else
        return a * temp * temp
    end
end

function BigInt.__eq(a, b)
    if #a ~= #b then return false end
    if a.sign ~= b.sign then return false end
    local i = 1
    local r = true
    while a[i] do
        if a[i] ~= b[i] then
            r = false
            break
        end
        i = i + 1
    end
    return r
end

function BigInt.__lt(a, b)
    return BigInt.__sub(a, b).sign == -1
end

function BigInt.__unm(a)
    local b = BigInt.clone(a)
    b.sign = a.sign * -1
    return b
end

function BigInt.__add(a, b)
    local a = BigInt(a)
    local b = BigInt(b)
    if a.sign == 1 and b.sign == 1 then
        return uadd(a, b)
    elseif a.sign == 1 and b.sign == -1 then
        return usub(a, b)
    elseif a.sign == -1 and b.sign == 1 then
        return usub(b, a)
    else
        local r = uadd(a, b)
        r.sign = -1
        return r
    end
end

function BigInt.__sub(a, b)
    local a = BigInt(a)
    local b = BigInt(b)
    if a.sign == 1 and b.sign == 1 then
        return usub(a, b)
    elseif a.sign == 1 and b.sign == -1 then
        return uadd(a, b)
    elseif a.sign == -1 and b.sign == 1 then
        local c = uadd(a, b)
        c.sign = -1
        return c
    else
        return usub(b, a)
    end
end

function BigInt.__mul(a, b)
    local a = BigInt(a)
    local b = BigInt(b)
    local c = BigInt()
    for i = 1, #a do
        local carry = 0
        for j = 1, #b do
            local k = i + j - 1
            local ai = a[i] or 0
            local bj = b[j] or 0
            local ck = c[k] or 0
            ck = ck + carry + ai * bj
            -- carry = ck // 10
            -- c[k] = ck % 10
            carry = math.floor(ck / 10)
            c[k] = math.fmod(ck, 10)
        end
        c[i+#b] = carry
    end
    c.sign = a.sign * b.sign
    trim(c)
    return c
end

function BigInt.__div(a, b)
    local a = BigInt(a)
    local b = BigInt(b)
    local q = udiv(a, b)
    q.sign = a.sign * b.sign
    trim(q)
    return q
end

function BigInt.__pow(a, b)
    local a = BigInt(a)
    local b = BigInt(b)
    return upow(a, b)
end

function BigInt:__tostring()
    local l = {}
    local i = 1
    -- trim(self)
    -- if #self == 1 and self[1] == "0" then return "0" end
    for j = #self, 1, -1 do
        l[i] = self[j]
        i = i + 1
    end
    -- trim(l)
    if self.sign == -1 then
        return "-"..table.concat(l)
    end
    return table.concat(l)
end

function BigInt:inc()
    -- in place
    if self.sign == -1 then
        udec(self)
    else
        uinc(self)
    end
end

function BigInt:dec()
    -- in place
    if self.sign == -1 then
        uinc(self)
    else
        udec(self)
    end
end

function BigInt:toBase()
end

function BigInt:fromBase()
end

function BigInt.divmod(a, b)
    local q, r = udiv(a, b)
    q.sign = a.sign * b.sign
    trim(q)
    trim(r)
    return q, r
end

function BigInt.clone(a)
    local o = {unpack(a)}
    o.sign = a.sign
    setmetatable(o, BigInt)
    return o
end

function BigInt:new(n)
    local o
    local t = type(n)
    if t == "number" then
        o = num2tab(math.floor(n))
    elseif t == "string" then
        o = str2tab(n)
    elseif t == "table" then
        if n.__tostring == self.__tostring then return n end
        o = {unpack(n)}
    else
        o = {0, sign=1}
    end
    setmetatable(o, BigInt)
    return o
end

setmetatable(BigInt, {__call=BigInt.new})
return BigInt