-- SPDX-FileCopyrightText: Copyright (c) 2019 Michał Wróblewski
-- This file is distributed under an MIT license.
-- For more information, see the following file in the LICENSES directory:
-- SPDX-License-Identifier: LicenseRef-MIT-X-Lua-BigInt

BigInt={}
BigInt.__index=BigInt

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

function BigInt.new(str)
	if getmetatable(str)==BigInt then return str end
	local self=setmetatable({},BigInt)
	self.digits={}
	for digit in tostring(str):gmatch'[0-9]' do
		table.insert(self.digits,tonumber(digit))
	end
	self.signed=tostring(str):sub(1,1)=='-'
	return self
end
function BigInt.clone(self)
	return BigInt(tostring(self))
end
function BigInt:__tostring()
	return (self.signed and '-' or '')..table.concat(self.digits)
end
function BigInt:__len()
	return #self.digits
end
function BigInt:__unm()
	local result=self:clone()
	result.signed=not result.signed
	return result
end
function BigInt.__add(a,b)
	if getmetatable(a)~=BigInt or getmetatable(b)~=BigInt then return BigInt(a)+BigInt(b) end
	if a.signed and b.signed then
		return -(-a+-b)
	elseif a.signed or b.signed then
		return -(a:abs()-b:abs())
	end
	local result={}
	local carry=0
	local max_digits=(#a>#b and #a or #b)
	for i=0,max_digits-1 do
		result[max_digits-i]=(a.digits[#a-i] or 0)+(b.digits[#b-i] or 0)+carry
		carry=(result[max_digits-i]>9 and 1 or 0)
		result[max_digits-i]=result[max_digits-i]%10
	end
	return BigInt((carry==1 and 1 or '')..table.concat(result))
end
function BigInt.__sub(a,b)
	if getmetatable(a)~=BigInt or getmetatable(b)~=BigInt then return BigInt(a)-BigInt(b) end
	if a<b then
		return -(b-a)
	elseif a.signed and b.signed then
		return -b-(-a)
	elseif a.signed or b.signed then
		return a:abs()+b:abs()
	end
	local result={}
	local borrow=0
	for i=0,#a-1 do
		result[#a-i]=(a.digits[#a-i] or 0)-(b.digits[#b-i] or 0)-borrow
		borrow=(result[#a-i]<0 and 1 or 0)
		result[#a-i]=(borrow==1 and result[#a-i]+10 or result[#a-i])
	end
	while #result>1 and result[1]==0 do
		table.remove(result,1)
	end
	return BigInt(table.concat(result))
end
function BigInt.__mul(a,b)
	if getmetatable(a)~=BigInt or getmetatable(b)~=BigInt then return BigInt(a)*BigInt(b) end
	if a==BigInt(0) or b==BigInt(0) then
		return BigInt(0)
	elseif a.signed and b.signed then
		return -a*-b
	elseif a.signed or b.signed then
		return -(a:abs()*b:abs())
	end
	local result=BigInt(0)
	for i=0,#a-1 do
		local carry=0
		local product={}
		for j=0,#b-1 do
			product[#b-j]=(a.digits[#a-i] or 0)*(b.digits[#b-j] or 0)+carry
			carry=product[#b-j]//10
			product[#b-j]=product[#b-j]%10
		end
		for k=1,i do
			table.insert(product,0)
		end
		result=result+((carry>0 and carry or '')..table.concat(product))
	end
	return result
end
function BigInt.__div(a,b)
	if getmetatable(a)~=BigInt or getmetatable(b)~=BigInt then return BigInt(a)/BigInt(b) end
	if a==BigInt(0) or b==BigInt(0) or a<b then
		return BigInt(0)
	elseif a.signed and b.signed then
		return -a/-b
	elseif a.signed or b.signed then
		return -(a:abs()/b:abs())
	end
	local result={}
	local dividend=BigInt(a.digits[1])
	while dividend<=b and a.digits[#dividend+1] ~= nil do
		dividend.digits[#dividend+1]=a.digits[#dividend+1]
	end
	local digit=#dividend
	for i=1,#a-digit+1 do
		result[i]=b+b<=dividend and 1 or 0
		while (result[i]+1)*b<=dividend do
			result[i]=result[i]+1
		end
		dividend=dividend-(b*result[i])
		dividend.digits[#dividend+(dividend~=BigInt(0) and 1 or 0)]=a.digits[digit+i]
	end
	return BigInt(table.concat(result))
end
function BigInt.__pow(a,b)
	if getmetatable(a)~=BigInt or getmetatable(b)~=BigInt then return BigInt(a)^BigInt(b) end
	local result=BigInt(1)
	while b~=BigInt(0) do
		result=result*a
		b=b-1
	end
	return result
end
function BigInt.__mod(a,b)
	return a<b and a or a-(b*(a/b))
end
function BigInt.__eq(a,b)
	return not (a>b or a<b)
end
function BigInt.__lt(a,b)
	if getmetatable(a)~=BigInt or getmetatable(b)~=BigInt then return BigInt(a)<BigInt(b) end
	if a.signed and b.signed then
		return -a>-b
	elseif a.signed or b.signed then
		return a.signed
	else
		if #a~=#b then
			return #a<#b
		else
			for i=1,#a do
				if a.digits[i]~=b.digits[i] then
					return a.digits[i]<b.digits[i]
				end
			end
			return false
		end
	end
end
function BigInt:abs()
	return (self.signed and -self or self)
end