123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215namespace BigInt {
	using namespace std;
	class INT {
	private:
		int a[10005]; // 倒序高精度数组
		int len; // 高精数字位数（长度）
		bool f = false; // 负数标记（0 为正，1 为负）
		void copy(int a[]) { // 将倒序数组 a 正序存储到正序数组 n 中
			memset(n, 0, sizeof n);
			for (int a_len = len, n_len = 1; a_len >= 1; a_len--, n_len++)
				n[n_len] = a[a_len];
		}
	public:
		int n[10005]; // 正序高精度数组
		INT(long long x = 0) { // 构造函数（整型转高精）
			f = false;
			if (x < 0) {
				f = true;
				x = -x;
			}
			memset(a, 0, sizeof a);
			for (len = 1; x; len++) {
				a[len] = x % 10;
				x /= 10;
			}
	        len--;
	        copy(a);
		}
		INT(string s) { // 构造函数（字符串转高精）
			f = false;
			if (s[0] == '-') {
				f = true;
				s.replace(0, 1, "");
			}
			memset(a, 0, sizeof a);
			for (len = 1; !s.empty(); len++) {
				a[len] = s[s.size() - 1] - '0';
				s.erase(s.size() - 1);
			}
	        len--;
	        copy(a);
		}
		inline int size() { // 获取数字位数
			return len;
		}
		bool operator >(INT b) { // 大于号重载
			if (f && !b.f) {
				return false;
			} else if (!f && b.f) {
				return true;
			} else if (f && b.f) {
				INT a = *this;
				INT t = a;
				a = b, b = t;
			}
			if (len != b.len)
				return len > b.len;
			else
				for (int i = len; i >= 1; i--)
					if (a[i] != b.a[i])
						return a[i] > b.a[i];
		}
		bool operator ==(INT b) { // 等于号重载
			if ((f && !b.f) || (!f && b.f) || len != b.len)
				return false;
			for (int i = 1; i <= len; i++)
				if (a[i] != b.a[i])
					return false;
			return true;
		}
		bool operator <(INT b) { // 小于号重载
			return !(*this > b) && !(*this == b);
		}
		bool operator >=(INT b) { // 大于等于重载
			return (*this > b) || (*this == b);
		}
		bool operator <=(INT b) { // 小于等于重载
			return (*this < b) || (*this == b);
		}
		bool operator !=(INT b) { // 不等于重载
			return !(*this == b);
		}
		INT Iabs() { // 绝对值
			INT n = *this;
			if (n.f) n.f = false;
			return n;
		}
		INT operator +(INT b) { // 高精加高精
			INT a = *this, c;
			if (a.f == b.f) {
				c.f = a.f;
				a = a.Iabs(), b = b.Iabs();
			} else {
				if (a.Iabs() > b.Iabs()) {
					c = a.Iabs() - b.Iabs();
					c.f = a.f;
				} else if (b.Iabs() > a.Iabs()) {
					c = b.Iabs() - a.Iabs();
					c.f = b.f;
				} else {
					return 0;
				}
				return c;
			}
			c.len = max(a.len, b.len) + 1;
			for (int i = 1; i <= c.len; i++) c.a[i] = a.a[i] + b.a[i];
			for (int i = 1; i <= c.len; i++)
				if (c.a[i] >= 10) {
					c.a[i + 1]++;
					c.a[i] -= 10;
				}
			while (!c.a[c.len] && c.len > 1) c.len--;
			c.copy(c.a);
			return c;
		}
		INT operator +(int B) { // 高精加低精
			INT b(B);
			return *this + b;
		}
		INT operator -(INT b) { // 高精减高精
			INT a = *this, c;
			if (a.f == true || b.f == true) {
				c = a + (-b);
				return c;
			}
			if (a < b) {
				INT t = a;
				a = b, b = t;
				c.f = true;
			}
			c.len = max(a.len, b.len);
			for (int i = 1; i <= c.len; i++) c.a[i] = a.a[i] - b.a[i];
			for (int i = 1; i <= c.len; i++)
				if (c.a[i] < 0) {
					c.a[i + 1]--;
					c.a[i] += 10;
				}
			while (!c.a[c.len] && c.len > 1) c.len--;
			c.copy(c.a);
			return c;
		}
		INT operator -(int B) { // 高精减低精
			INT b(B);
			return (*this - b);
		}
		INT operator -() { // 负号重载
			INT b = *this;
			b.f = !b.f;
			return b;
		}
		INT operator *(INT b) { // 高精乘高精
			INT a = *this, c;
			if (a.f == b.f) {
				a = a.Iabs(), b = b.Iabs();
			} else {
				a = a.Iabs(), b = b.Iabs();
				c.f = true;
			}
			c.len = a.len + b.len;
			for (int i = 1; i <= a.len; i++)
				for (int j = 1; j <= b.len; j++)
					c.a[i + j - 1] += a.a[i] * b.a[j];
			for (int i = 1; i <= c.len; i++)
				if (c.a[i] >= 10) {
					c.a[i + 1] += c.a[i] / 10;
					c.a[i] %= 10;
				}
			while (!c.a[c.len] && c.len > 1) c.len--;
			c.copy(c.a);
			return c;
		}
		INT operator *(int B) { // 高精乘低精
			INT b(B);
			return *this * b;
		}
		INT operator /(int b) { // 高精度除法
			INT a = *this, c;
			if (a.f)
				c.f = b > 0;
			else
				c.f = b < 0;
			a = a.Iabs(), b = abs(b);
			int x = 0;
			for (int i = len; i >= 1; i--) {
				c.a[c.len++] = (x * 10 + a.a[i]) / b;
				x = (x * 10 + a.a[i]) % b;
			}
			while (c.a[c.len] == 0 && c.len > 1) c.len--;
			c.copy(c.a);
			return c;
		}
		int operator %(int b) { // 取余
			INT a = *this;
			int x = 0, f = (a.f ? -1 : 1);
			a = a.Iabs(), b = abs(b);
			for (int i = len; i >= 1; i--)
				x = (x * 10 + a.a[i]) % b;
			return x * f;
		}
		void read() { // 读入字符串为高精数字
			string s;
			cin >> s;
			*this = INT(s);
		}
		void print() { // 输出高精数字
			if (f && n[1] != 0) printf("-");
			for (int i = 1; i <= len; i++) printf("%d", n[i]);
		}
	};
	struct INTgreater { // 倒序排序规则
		bool operator ()(INT a, INT b) {
			return a > b;
		}
	};
}