#ifndef BIGINT_HPP
#define BIGINT_HPP
#include <cstdint>
#include <deque>
#include <string>
#include <cmath>
#include <bitset>
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(unsigned long long n, size_t _size) : data(_size, 0){
		data[_size - 1] = l(n);
		data[_size - 2] = 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 uint64_t mod(uint64_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;
	}
	void trim(){
		while(!(data[1] | data[0]))data.pop_front();
	}
	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++){
			carry = 0;
			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;
		if(false)
		for(size_t i = 0;i < matrix.size();i++){
			for(size_t ih = 0;ih < matrix.size();ih++){
				std::cout << matrix[i][ih] << " ";
			}
			std::cout << std::endl;
		}
		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);
		}
		ret.trim();
		return ret;
	}
	
	inline BigInt& bitshiftLeft(int c){
		if(c < 0)return bitshiftRight(-c);
		int jump = c / 32;
		int sh = c % 32;
		for(int i = 0;i < (int)(size()) - jump;i++){
			data[i] = l(data[i + jump] << sh);
			if(i < size() - jump - 1){
				data[i] |= data[i + jump + 1] >> (32 - sh);
			}
		}
		for(int i = std::max(0,(int)(size()) - jump);i < size();i++){
			data[i] = 0;
		}
		return *this;
	}
	
	inline BigInt& bitshiftRight(int c){
		if(c < 0)return bitshiftLeft(-c);
		unsigned int jump = c / 32;
		unsigned int sh = c % 32;
		for(unsigned int i = size() - 1;i >= jump;i--){
			data[i] = data[i - jump] >> sh;
			if(i > jump){
				data[i] |= l(data[i - jump - 1] << (32 - sh));
			}
		}
		for(int i = jump - 1;i >= 0;i--){
			data[i] = 0;
		}
		return *this;
	}
	inline BigInt& chunkshiftLeft(int c){
		if(c < 0)return chunkshiftRight(-c);
		for(int i = 0;i < (int)(size()) - c;i++){
			data[i] = data[i + c];
		}
		for(int i = std::max(0,(int)(size()) - c);i < size();i++){
			data[i] = 0;
		}
		return *this;
	}
	
	inline BigInt& chunkshiftRight(int c){
		if(c < 0)return chunkshiftLeft(-c);
		for(int i = size() - 1;i >= c;i--){
			data[i] = data[i - c];
		}
		for(int i = c - 1;i >= 0;i--){
			data[i] = 0;
		}
		return *this;
	}
	
	inline size_t size()const{
		return data.size();
	}
	inline bool operator==(const BigInt& o)const{
		auto it1 = data.rbegin();
		auto it2 = o.data.rbegin();
		while(true){
			if(*(it1++) != *(it2++))return false;
			if(it1 == data.rend())return true;
			if(it2 == o.data.rend())return true;
		}
	}
	inline bool isZero(){
		for(uint64_t d : data){
			if(d)return false;
		}
		return true;
	}
	inline std::string bitString(){
		std::vector<char> _bits;
		_bits.reserve(data.size() * 32);
		for(uint64_t i : data){
			std::bitset<64> bits(i);
			for(int ih = 0;ih < 32;ih++)
			_bits.push_back((bits[32 - ih - 1] == 1) ? '1' : '0');
		}
		return std::string(_bits.begin(), _bits.end());
	}
	inline std::string rawString(){
		std::string a = "";
		for(uint64_t d : data){
			a += (std::to_string(d) + "|");
		}
		return a;
	}
	inline std::string toString(){
		std::string a = "";
		BigInt dec(*this);
		while(!dec.isZero()){
			a = std::to_string(dec.mod(10)) + a;
			dec = dec.div(10);
		}
		return a;
	}
};
#endif //BIGINT_HPP