#ifndef BIGINT_HPP
#define BIGINT_HPP
#include <cstdint>
#include <deque>
#include <string>
#include <cmath>
using std::size_t;
inline std::uint32_t u(uint64_t a){
	return (uint32_t)(a >> 32);
}
inline std::uint32_t l(uint64_t a){
	return (uint32_t)(a & 0x00000000FFFFFFFF);
}
template<typename T>
inline int signum(T t){
	if(t > 0)return 1;
	if(t < 0)return -1;
	return 0;
}
struct BigInt{
	using uint64_t = std::uint64_t;
	using uint32_t = std::uint32_t;
	int signum;
	std::deque<std::uint64_t> data;
	inline BigInt(size_t size, bool dummy) : data(size, 0){
		
	}

	inline BigInt(unsigned int n) : data(1, 0){
		data[0] = n;
	}
	inline BigInt(unsigned long long n) : data(2, 0){
		data[1] = l(n);
		data[0] = u(n);
	}
	inline BigInt(int n) : data(1, 0){
		data[0] = std::abs(n);
		signum = ::signum(n);
	}
	inline BigInt(long long n) : data(2, 0){
		data[1] = l(std::abs(n));
		data[0] = u(std::abs(n));
		signum = ::signum(n);
	}
	inline uint32_t mod(uint32_t o){
		uint64_t carry = 0;
		for(size_t i = 0;i < data.size();i++){
			carry = ((carry << 32) + data[i]) % o;
		}
		return carry;
	}
	inline BigInt div(uint32_t o){
		uint64_t carry = 0;
		BigInt ret = *this;
		for(size_t i = 0;i < data.size();i++){
			ret.data[i] = (data[i] + (carry << 32)) / o;
			carry = (data[i] + (carry << 32)) % o;
		}
		return ret;
	}
	
	inline BigInt add(const BigInt& other){
		BigInt ret((size_t)std::max((size_t)data.size(), (size_t)other.data.size()), false);
		uint64_t carry = 0;
		for(size_t s = 0;s < std::max(data.size(), other.data.size());s++){
			uint64_t s1 = (s >= data.size() ? 0 : data[data.size() - s - 1]);
			uint64_t s2 = (s >= other.size() ? 0 : other.data[other.size() - s - 1]);
			uint64_t sum = s1 + s2 + carry;
			ret.data[ret.size() - s - 1] = l(sum);
			carry = u(sum);
		}
		return ret;
	}
	
	inline BigInt mult(const BigInt& other){
		std::deque<std::deque<uint64_t>> matrix(size(), std::deque<uint64_t>(other.size() + 1, 0));
		uint64_t carry = 0;
		BigInt ret(size() + other.size(), false);
		for(size_t i = 0;i < size();i++){
			for(size_t ih = 0;ih < other.size();ih++){
				uint64_t res = data[size() - i - 1] * other.data[other.size() - ih - 1];
				res += carry;
				matrix[i][ih] = l(res);
				carry = u(res);
			}
		}
		carry = 0;
		for(size_t column = 0;column < (matrix.size() + other.size());column++){
			uint64_t accum = 0;
			for(size_t row = 0;row < matrix.size();row++){
				if(row > column)goto end;
				else if(column - row < matrix[row].size()){
					accum += matrix[row][column - row];
				}
			}
			end:
			accum += carry;
			carry = u(accum);
			ret.data[ret.size() - column - 1] = l(accum);
		}
		if(ret.data[0] == 0)ret.data.pop_front();
		return ret;
	}
	inline size_t size()const{
		return data.size();
	}
	inline std::string toString(){
		std::string a = "";
		BigInt dec(*this);
		while(dec.data[dec.data.size() - 1]){
			a = std::to_string(dec.mod(10)) + a;
			dec = dec.div(10);
		}
		return a;
	}
};
#endif