#include<bits/stdc++.h>
using namespace std;
#define maxk_of_vector 1000000000
#define my (*this)
class big {
		std::deque<unsigned long long>v;
		/*00 00 22 55*/
		/* 表示 2255*/
		inline void ZERO_CLEAR__alg(deque<unsigned long long>v = v) {
			/*去0*/
			while (!v[0])v.pop_front();
		}
		inline void ZERO_ON_INT__alg(unsigned x, deque<unsigned long long>v = v) {
			/*加0*/
			while (v.size() < x)v.push_front(0);
		}
		inline void REMOVE_ARR__alg(deque<unsigned long long>v = v) {
			/*反转*/
			stack<int>x;
			while (v.size())x.push(v.front());
			while (x.size()) {
				v.push_front(x.top());
				x.pop();
			}
		}
		inline void EQAUL_STRING__alg(string x) {
			v.clear();
			stack<char>c;
			while (x.size()) {
				c.push(x.back() ^ 48);
				x.pop_back();
			}
			unsigned long long d = 0;
			while (c.size()) {
				if (d * 10 >= maxk_of_vector)v.push_back(d), d = 0;
				d = d << 3 + d << 1 + c.top();
			}
		}
		deque<unsigned long long> mul(deque<unsigned long long> &a, deque<unsigned long long> &b) {
			deque<unsigned long long> ans(a.size() + b.size() + 1, 0); // 初始化结果数组
			REMOVE_ARR__alg(a);
			REMOVE_ARR__alg(b);
			// 标准竖式乘法
			for (int i = 0; i < a.size(); i++) {
				unsigned long long carry = 0;
				for (int j = 0; j < b.size(); j++) {
					unsigned long long tmp = a[i]   b[j]   carry;
					ans[i + j] += tmp;
					carry = ans[i + j] / maxk_of_vector;
					ans[i + j] %= maxk_of_vector;
				}
				if (carry) ans[i + b.size()] += carry;
			}
			REMOVE_ARR__alg(ans);
			ZERO_CLEAR__alg(ans);
			return ans;
		}

	public :
		big(std::string x) {
			EQAUL_STRING__alg(x);
		}
		big(unsigned long long x) {
			v.clear();
			v.push_back(x);
		}
		big(long long x) {
			v.clear();
			v.push_back(x);
		}
		big(unsigned long x) {
			v.clear();
			v.push_back(x);
		}
		big(short x) {
			v.clear();
			v.push_back(x);
		}
		big(unsigned short x) {
			v.clear();
			v.push_back(x);
		}
		big(char x) {
			v.clear();
			v.push_back(x);
		}
		big(unsigned char x) {
			v.clear();
			v.push_back(x);
		}
		big(big x) {
			v = x.v;
		}
		~big() {
			v.clear();
		}
		inline void operator = (unsigned long long x) {
			v.clear();
			v.push_back(x);
		}
		inline void operator = (long long x) {
			v.clear();
			v.push_back(x);
		}
		inline void operator = (unsigned long x) {
			v.clear();
			v.push_back(x);
		}
		inline void operator = (long x) {
			v.clear();
			v.push_back(x);
		}
		inline void operator = (unsigned short x) {
			v.clear();
			v.push_back(x);
		}
		inline void operator = (short x) {
			v.clear();
			v.push_back(x);
		}
		inline void operator = (big x) {
			v = x.v;
		}
		inline void operator >>=(unsigned long long wei);
		inline void operator <<=(unsigned long long wei);
		inline big operator >>(unsigned long long wei);
		inline big operator <<(unsigned long long wei);
		inline big operator +(big x);
		inline big operator -(big x);
		inline big operator *(big x);
		inline big operator /(big x);
		inline big operator %(big x);
		inline void operator +=(big x);
		inline void operator -=(big x);
		inline void operator *=(big x);
		inline void operator /=(big x);
		inline void operator %=(big x);
		inline bool operator ==(big x) {
			auto i = v.begin();
			auto j = x.v.begin();
			if (x.v.size() == v.size())while (i != v.end()) {
					if (*i ^ *j)return false;
					++i;
					++j;
				} else return false;
			return true;
		}
		inline bool operator >=(big x) {
			auto i = v.begin();
			auto j = x.v.begin();
			if (x.v.size() == v.size())while (i != v.end()) {
					if (*i < *j)return false;
					++i;
					++j;
				} else return v.size() >= x.v.size();
			return true;

		}
		inline bool operator <=(big x) {
			return !(my == x || my < x);
		}
		inline bool operator !=(big x) {
			return !(my == x);
		}
		inline bool operator >(big x) {
			return !(my <= x);
		}
		inline bool operator <(big x) {
			return !(my >= x);
		}
};
/*高精度*/