#ifndef BIG_INT_HPP
#define BIG_INT_HPP
#include "semi_bitset.hpp"
#include <cstdlib>
#include <string>
template<size_t size>
class BigInt{
private:
	int signum = 1;
	semi_bitset<size, size >= 1000> bits;
public:
	inline BigInt(){
		
	}
	inline BigInt(int o){
		if(o < 0){signum = -1;o *= -1;}
		bits.data[bits.length() - 1] = (unsigned int)o;
	}
	inline BigInt(unsigned int o){
		bits.data[bits.length() - 1] = o;
	}
	inline BigInt(long long o){
		if(o < 0){signum = -1;o = 0ULL - o;}
		bits.data[bits.length() - 1] = (o & lower_half);
		bits.data[bits.length() - 2] = (o >> 32);
	}
	inline BigInt(unsigned long long o){
		bits.data[bits.length() - 1] = (o & lower_half);
		bits.data[bits.length() - 2] = (o >> 32);
	}
	template<std::size_t osize>
	inline BigInt<size> add(const BigInt<osize>& o)const{
		static_assert(size == osize);
		BigInt<size> ret;
		uint64_t carry = 0;
		for(size_t i = size - 1;i >= 0;i--){
			uint64_t res = (*this)[i] + o[i] + carry;
			carry = (res >> 32);
			ret[i] = res & lower_half;
			if(i == 0)break;
		}
		return ret;
	}
	template<size_t osize>
	inline BigInt<size> mult(const BigInt<osize>& o)const{
		BigInt<size + osize> ret;
		uint64_t mat[size][size] = {0};
		uint64_t carry = 0;
		for(size_t i = 0;i < size;i++){
			for(size_t ih = size - 1;ih != ~(0ULL);ih--){
				mat[i][ih] = (*this)[i] * o[ih] + carry;
				carry = mat[i][ih] >> 32;
				mat[i][ih] &= lower_half;
				if(ih == 0)break;
			}
		}
		carry = 0;
		for(size_t i = size - 1;i != ~(0ULL);i--){
			uint64_t accum = 0;
			for(size_t ih = 0;ih < size;ih++){
				accum += ((i + ih) >= size) ?  0 : mat[i + ih][ih];
			}
			accum += carry;
			ret[i] = accum & lower_half;
			carry = accum >> 32;
		}
		return ret;
	}
	
	inline BigInt<size> div(unsigned int o)const{
		uint64_t carry = 0;
		BigInt<size> ret;
		for(size_t i = 0;i < size;i++){
			uint64_t res = ((*this)[i] + (carry << 32)) / o;
			carry = (*this)[i] % o;
			ret[i] = res;
		}
		return ret;
	}
	inline unsigned int mod(unsigned int o)const{
		uint64_t carry = 0;
		for(size_t i = 0;i < size;i++){
			carry = (this->operator[](i) + (carry << 32)) % o;
		}
		return (unsigned int)(carry & lower_half);
	}
	inline std::uint64_t& operator[](size_t i){
		return bits.data[i];
	}
	
	inline const std::uint64_t& operator[](size_t i)const{
		return bits.data[i];
	}
	inline bool isZero()const{
		for(size_t i = 0;i < size;i++){
			if(this->operator[](i))return false;
		}
		return true;
	}
	template<typename stream, size_t osize>
	inline friend stream& operator<<(stream& s, const BigInt<osize>& o){
		std::string a = "";
		BigInt dis = o;
		while(!dis.isZero()){
			a = std::to_string(dis.mod(10)) + a;
			dis = dis.div(10);
		}
		return s << a;
	}
};
#endif