#ifndef BIGINT64_HPP
#define BIGINT64_HPP
#include <cstdint>
#include <cstdlib>
#include <algorithm>
#include <iterator>
#include <initializer_list>
#include <deque>
#include <vector>
#include <string>
#include <cmath>
#include <bitset>
#include <iostream>
const std::vector<char> chars = {'0','1','2','3','4','5','6','7','8','9'};
const __uint128_t _m = ((__uint128_t)1) << 64;
template<typename T>
inline int signum(T t){
	if(t < 0)return -1;
	if(t >= 0)return 1;
}
inline std::ostream& operator<<(std::ostream& out, __uint128_t o){
	if(o == 0)return out << "0";
	while(o > 0){
		out << std::to_string((int)(o % 10));
		o /= 10;
	}
	return out;
}
struct BigInt{
	using size_t = std::size_t;
	using ssize_t = std::int64_t;
	using uint64_t = std::uint64_t;
	using uint32_t = std::uint32_t;
	using lui = ::__uint128_t;
	std::deque<uint64_t> data;
	int signum;
	inline BigInt() : data(1,0),signum(1){}
	inline BigInt(size_t _s, uint64_t fill) : data(_s,fill), signum(1){}
	inline BigInt(int a) : signum(::signum(a)), data(1, std::abs(a)){}
	inline BigInt(unsigned int a) : signum(1), data(1, a){}
	inline BigInt(unsigned long long a) : signum(1), data(1, a){}
	inline BigInt(long long a) : signum(::signum(a)), data(1, std::abs(a)){}
	inline BigInt(const std::initializer_list<uint64_t>& l) : data(l), signum(1){}
	inline BigInt(std::initializer_list<uint64_t>&& l) : data(std::move(l)), signum(1){}
	template<typename InputIterator>
	inline BigInt(InputIterator begin, InputIterator end) : data(begin, end), signum(1){}
	std::deque<uint64_t>::iterator begin(){return data.begin();}
	std::deque<uint64_t>::iterator end(){return data.end();}
	std::deque<uint64_t>::reverse_iterator rbegin(){return data.rbegin();}
	std::deque<uint64_t>::reverse_iterator rend(){return data.rend();}
	std::deque<uint64_t>::const_iterator begin()const{return data.begin();}
	std::deque<uint64_t>::const_iterator end()const{return data.end();}
	std::deque<uint64_t>::const_reverse_iterator rbegin()const{return data.rbegin();}
	std::deque<uint64_t>::const_reverse_iterator rend()const{return data.rend();}
	size_t size()const{return data.size();}
	auto cbegin(){return data.cbegin();}
	auto cend(){return data.cend();}
	auto crbegin(){return data.crbegin();}
	auto crend(){return data.crend();}
	auto cbegin()const{return data.cbegin();}
	auto cend()const{return data.cend();}
	auto crbegin()const{return data.crbegin();}
	auto crend()const{return data.crend();}
	inline bool isZero()const{
		for(auto it = data.begin();it != data.end();it++){
			if(*it)return false;
		}
		return true;
	}
	inline void setZero(){
		for(auto it = begin();it != end();it++)*it = 0;
	}
	inline void trim(){
		while(data[0] == 0 && data.size() != 0){
			data.pop_front();
		}
	}
	inline BigInt div(uint64_t d)const{
		BigInt ret = *this;
		lui carry = 0;
		for(auto it = ret.data.begin();it != ret.data.end();it++){
			lui temp = (lui)*it;
			temp += carry;
			carry = temp % d;
			*it = (uint64_t)(temp / d);
			carry <<= 64;
		}
	}
	inline BigInt& div(uint64_t d){
		lui carry = 0;
		for(auto it = data.begin();it != data.end();it++){
			lui temp = (lui)*it;
			temp += carry;
			carry = temp % d;
			*it = (uint64_t)(temp / d);
			carry <<= 64;
		}
	}
	inline uint64_t mod(uint64_t m)const{
		lui carry = 0;
		for(auto it = data.begin();it != data.end();it++){
			carry <<= 64;
			carry = (*it + carry) % m;
		}
		return carry;
	}
	inline BigInt& chunkshiftLeft(int c){
		if(c < 0)return chunkshiftRight(-c);
		if(c >= size()){std::fill(begin(),end(),0);return *this;}
		auto it1 = data.begin(); 
		auto it2 = it1 + c;
		while(it2 != data.end())*(it1++) = *(it2++);
		while(it1 != data.end())*(it1++) = 0;
		return *this;
	}
	inline BigInt& chunkshiftRight(int c){
		if(c < 0)return chunkshiftLeft(-c);
		if(c >= size()){std::fill(begin(),end(),0);return *this;}
		auto it1 = data.rbegin(); 
		auto it2 = it1 + c;
		while(it2 != data.rend())*(it1++) = *(it2++);
		while(it1 != data.rend())*(it1++) = 0;
		return *this;
	}
	inline BigInt& adda(const BigInt& o){
		while(size() < o.size())data.push_front(0);
		bool carry = 0;
		auto it1 = rbegin();
		auto it2 = o.rbegin();
		while(it1 != rend() && it2 != o.rend()){
			carry = __builtin_uaddll_overflow(*it1, *it2 + carry, (unsigned long long*)(&(*it1)));
			carry |= (*it2 + carry) == 0 && *it2;
			it1++;
			it2++;
		}
		while(it1 != rend() && carry){
			carry = __builtin_uaddll_overflow(*it1, carry, (unsigned long long*)(&(*it1)));
		}
		if(carry)data.push_front(1);
		return *this;
	}
	
	inline BigInt mult(const BigInt& o){
		BigInt result(size() + o.size(),0);
		BigInt temp(size() + o.size(),0);
		int p = 0;
		for(auto it1 = rbegin();it1 != rend();it1++){
			auto it = temp.rbegin();
			lui carry = 0;
			for(auto it2 = o.rbegin();it2 != o.rend();it2++){
				lui prod = ((lui)*it1) * (*it2);
				prod += carry;
				*(it++) = (uint64_t)prod;
				carry = (prod >> 64);
			}
			if(carry)(*it)++;
			temp.chunkshiftLeft(p++);
			result.adda(temp);
			temp.setZero();
		}
		result.trim();
		return result;
	}
	
	inline std::string toString(){
		std::vector<char> c_str;
		c_str.reserve(data.size() * 19);
		BigInt diver = *this;
		while(!diver.isZero()){
			c_str.push_back(chars.at(diver.mod(10)));
			diver.div(10);
		}
		return std::string(c_str.rbegin(), c_str.rend());
	}
};
#endif //BIGINT64_HPP