#ifndef BIGINT64_HPP
#define BIGINT64_HPP
#include <cstdint>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <iterator>
#include <limits>
#include <initializer_list>
#include <deque>
#include <vector>
#include <string>
#include <bitset>
#include <iostream>
const std::vector<char> chars = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
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;
	using iterator = std::deque<uint64_t>::iterator;
	using const_iterator = std::deque<uint64_t>::const_iterator;
	using reverse_iterator = std::deque<uint64_t>::reverse_iterator;
	using const_reverse_iterator = std::deque<uint64_t>::const_reverse_iterator;
	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) :  data(1, std::abs(a)),signum(::signum(a)){}
	inline BigInt(unsigned int a) : data(1, a),signum(1){}
	inline BigInt(unsigned long long a) : data(1, a), signum(1){}
	inline BigInt(long long a) : data(1, std::abs(a)),signum(::signum(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){}
	inline BigInt(const BigInt& o) : data(o.data), signum(o.signum){}
	inline BigInt(BigInt&& o) : data(std::move(o.data)), signum(o.signum){}
	template<typename InputIterator>
	inline BigInt(InputIterator begin, InputIterator end) : data(begin, end), signum(1){}
	template<typename RNG>
	inline BigInt(RNG& rng, size_t length) : data(length, 0), signum(1){auto it = data.begin();while(it != data.end())*(it++) = rng();}
	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();}
	BigInt& operator=(const BigInt& o){
		data = o.data;
		signum = o.signum;
	}
	BigInt& operator=(BigInt&& o){
		data = std::move(o.data);
		signum = o.signum;
	}
	uint64_t& operator[](size_t i){return data[i];}
	const uint64_t& operator[](size_t i)const{return data[i];}
	size_t size()const{return data.size();}
	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 operator<(const BigInt& o)const{
		if(signum > o.signum){
			return false;
		}
		if(signum < o.signum){
			return true;
		}
		const_iterator it1 = begin();
		const_iterator it2 = o.begin();
		if(size() > o.size()){
			it1 += size() - o.size();
			auto _t = begin();
			while(_t != it1){
				if(*_t)return false;
				++_t;
			}
		}
		else if(size() < o.size()){
			it2 += o.size() - size();
			auto _t = o.begin();
			while(_t != it2){
				if(*_t)return true;
				++_t;
			}
		}
		while(it1 != end() && it2 != o.end()){
			if(*(it1) < *(it2))return true;
			if(*(it1) > *(it2))return false;
			++it1;++it2;
		}
		return false;
	}
	inline bool operator>(const BigInt& o)const{
		if(signum < o.signum){
			return false;
		}
		if(signum > o.signum){
			return true;
		}
		const_iterator it1 = begin();
		const_iterator it2 = o.begin();
		if(size() > o.size()){
			it1 += size() - o.size();
			auto _t = begin();
			while(_t != it1){
				if(*_t)return true;
				++_t;
			}
		}
		else if(size() < o.size()){
			it2 += o.size() - size();
			auto _t = o.begin();
			while(_t != it2){
				if(*_t)return false;
				++_t;
			}
		}
		while(it1 != end() && it2 != o.end()){
			if(*(it1) > *(it2))return true;
			if(*(it1) < *(it2))return false;
			++it1;++it2;
		}
		return false;
	}
	inline bool operator<=(const BigInt& o)const{
		if(signum > o.signum){
			return false;
		}
		if(signum < o.signum){
			return true;
		}
		const_iterator it1 = begin();
		const_iterator it2 = o.begin();
		if(size() > o.size()){
			it1 += size() - o.size();
			auto _t = begin();
			while(_t != it1){
				if(*_t)return true;
				++_t;
			}
		}
		else if(size() < o.size()){
			it2 += o.size() - size();
			auto _t = o.begin();
			while(_t != it2){
				if(*_t)return false;
				++_t;
			}
		}
		while(it1 != end() && it2 != o.end()){
			if(*(it1) < *(it2))return true;
			if(*(it1) > *(it2))return false;
			++it1;++it2;
		}
		return true;
	}
	inline bool operator>=(const BigInt& o)const{
		if(signum < o.signum){
			return false;
		}
		if(signum > o.signum){
			return true;
		}
		const_iterator it1 = begin();
		const_iterator it2 = o.begin();
		if(size() > o.size()){
			it1 += size() - o.size();
			auto _t = begin();
			while(_t != it1){
				if(*_t)return true;
				++_t;
			}
		}
		else if(size() < o.size()){
			it2 += o.size() - size();
			auto _t = o.begin();
			while(_t != it2){
				if(*_t)return false;
				++_t;
			}
		}
		while(it1 != end() && it2 != o.end()){
			if(*(it1) > *(it2))return true;
			if(*(it1) < *(it2))return false;
			++it1;++it2;
		}
		return true;
	}
	inline bool operator==(const BigInt& o)const{
		if(signum < o.signum){
			return false;
		}
		if(signum > o.signum){
			return false;
		}
		const_iterator it1 = begin();
		const_iterator it2 = o.begin();
		if(size() > o.size()){
			it1 += size() - o.size();
			auto _t = begin();
			while(_t != it1){
				if(*_t)return false;
				++_t;
			}
		}
		else if(size() < o.size()){
			it2 += o.size() - size();
			auto _t = o.begin();
			while(_t != it2){
				if(*_t)return false;
				++_t;
			}
		}
		while(it1 != end() && it2 != o.end()){
			if(*(it1) != *(it2))return false;
			++it1;++it2;
		}
		return true;
	}
	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;
		}
		return ret;
	}
	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;
		}
		return *this;
	}
	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& bitshiftLeft(int c){
		if(c < 0)return bitshiftRight(-c);
		unsigned int sh = c % 64;
		unsigned int jmp = c / 64;
		if((unsigned int)jmp >= size()){std::fill(begin(),end(),0);return *this;}
		auto it1 = begin(); 
		auto it2 = it1 + jmp;
		auto beforeEnd = end() - 1;
		while(it2 != beforeEnd){
			*it1 = (*it2 << sh);
			if(sh)
			*it1 |= (*(it2 + 1) >> (64 - sh));
			++it1;++it2;
		}
		*it1 = (*it2 << sh);
		++it1;++it2;
		while(it1 != end()){
			*it1 = 0;
			++it1;
		}
		return *this;
	}
	
	inline BigInt& bitshiftRight(int c){
		if(c < 0)return bitshiftLeft(-c);
		unsigned int sh = c % 64;
		unsigned int jmp = c / 64;
		if((unsigned int)jmp >= size()){std::fill(begin(),end(),0);return *this;}
		auto it1 = rbegin(); 
		auto it2 = it1 + jmp;
		auto beforeRend = rend() - 1;
		while(it2 != beforeRend){
			*it1 = (*it2 >> sh);
			if(sh)
			*it1 |= (*(it2 + 1) << (64 - sh));
			++it1;++it2;
		}
		*it1 = (*it2 >> sh);
		++it1;++it2;
		while(it1 != rend()){
			*it1 = 0;
			++it1;
		}
		return *this;
	}
	BigInt operator<<(int c)const{
		BigInt ret = *this;
		ret.bitshiftLeft(c);
		return ret;
	}
	
	BigInt operator>>(int c)const{
		BigInt ret = *this;
		ret.bitshiftRight(c);
		return ret;
	}
	
	BigInt& operator<<=(int c){
		return bitshiftLeft(c);
	}
	BigInt& operator>>=(int c){
		return bitshiftRight(c);
	}
	int bitDifference(const BigInt& o){
		int pos1(-1),pos2(-1);
		auto it1 = begin();
		auto it2 = o.begin();
		while(it1 != end()){
			if(*it1 == 0)
				pos1 += 64;
			else{
				pos1 += __builtin_clzll(*it1);
				break;
			}
			++it1;
		}
		if(pos1 == -1)pos1 = size() * 64;
		while(it2 != end()){
			if(*it2 == 0)
				pos2 += 64;
			else{
				pos2 += __builtin_clzll(*it2);
				break;
			}
			++it2;
		}
		if(pos1 == -1)pos1 = o.size() * 64;
		int sizediff = ((signed int)size()) - ((signed int)o.size());
		return pos2 - pos1 + sizediff * 64;
	}
	inline BigInt& chunkshiftLeft(int c){
		if(c < 0)return chunkshiftRight(-c);
		if((unsigned int)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((unsigned int)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 bitshiftLeft(int c)const{
		if(c < 0)return bitshiftRight(-c);
		BigInt _this = *this;
		_this.bitshiftLeft(c);
		return _this;
	}
	inline BigInt bitshiftRight(int c)const{
		if(c < 0)return bitshiftLeft(-c);
		BigInt _this = *this;
		_this.bitshiftRight(c);
		return _this;
	}
	inline BigInt chunkshiftLeft(int c)const{
		if(c < 0)return chunkshiftRight(-c);
		BigInt _this = *this;
		_this.chunkshiftLeft(c);
		return _this;
	}
	inline BigInt chunkshiftRight(int c)const{
		if(c < 0)return chunkshiftLeft(-c);
		BigInt _this = *this;
		_this.chunkshiftRight(c);
		return _this;
	}
	inline BigInt add(const BigInt& o){
		BigInt ret = *this;
		ret.adda(o);
		return ret;
	}
	
	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)));
			++it1;
		}
		if(carry)data.push_front(1);
		return *this;
	}
	inline BigInt& suba(const BigInt& o){
		assert((*this) >= (o));
		bool carry = 0;
		auto it1 = rbegin();
		auto it2 = o.rbegin();
		while(it1 != rend() && it2 != o.rend()){
			carry = __builtin_usubll_overflow(*it1 - carry, *it2, (unsigned long long*)(&(*it1)));
			if(!carry)carry = ((*it1 - carry) == std::numeric_limits<uint64_t>::max());
			++it1;++it2;
		}
		while(it1 != rend() && carry){
			carry = __builtin_usubll_overflow(*it1, carry, (unsigned long long*)(&(*it1)));
			++it1;
		}
		return *this;
	}
	inline BigInt moda(){
		
	}
	inline BigInt mult(const BigInt& o)const{
		BigInt result(size() + o.size() + 1,0);
		BigInt temp(size() + o.size() + 1,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) += carry;
			temp.chunkshiftLeft(p++);
			result.adda(temp);
			temp.setZero();
		}
		result.trim();
		return result;
	}
	
	inline std::string rawString(){
		std::string s = "";
		bool flag;
		for(unsigned int i = 0;i < size();i++){
			if(data[i])flag = true;
			if(flag);
			s += std::to_string(data[i]);
			if(i < size() - 1)s += "|";
		}
		return s;
	}
	inline std::string bitString(){
		auto it = begin();
		std::string ret = "";
		std::cout << size() << "; " << std::flush;
		while(it != end()){
			std::bitset<64> bits(*it);
			for(unsigned int i = 0;i < 64;i++){
				ret += chars.at(((*it) & (1ULL << (64 - i))) != 0);
			}
			++it;
		}
		return ret;
	}
	inline std::string toString(){
		std::deque<char> c_str;
		const uint64_t q = 1000000000000000000ULL;
		//c_str.reserve(size() * 19);
		BigInt diver = *this;
		while(!diver.isZero()){
			std::string frac = std::to_string(diver.mod(q));
			int a = 0;
			for(auto it = frac.rbegin();it != frac.rend();it++){
				c_str.push_front(*it);
				a++;
			}
			while(a < 18){
				c_str.push_front('0');
				a++;
			}
			diver.div(q);
		}
		auto it = c_str.begin();
		while(*(it) == '0')++it;
		return std::string(it, c_str.end());
	}
	
	inline std::string toString(unsigned int base){
		std::vector<char> c_str;
		c_str.reserve(size() * (unsigned int)(64.0 * std::log(2) / std::log((double)base)));
		BigInt diver = *this;
		while(!diver.isZero()){
			c_str.push_back(chars.at(diver.mod(base)));
			diver.div(base);
		}
		return std::string(c_str.rbegin(), c_str.rend());
	}
};
namespace std{
	template<>
	struct hash<BigInt>{
		size_t operator()(const BigInt& o){
			size_t ret = 0;
			std::for_each(o.begin(), o.end(), [&ret](const uint64_t& ui){ret ^= ui;});
			return ret;
		}
	};
}
#endif //BIGINT64_HPP