#include<bits/stdc++.h>
#define Open(i) freopen(i".in", "r", stdin), freopen(i".out", "w", stdout);
#define Quick ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define FOR(i, l, r) for (int i = (l); i < (r); i++)
#define ROF(i, l, r) for (int i = (l) - 1; i >= (r); i--)
#ifndef ONLINE_JUDGE
	#include "algo/debug.h"
#else
	#define debug(...) 42
	#define debug2(...) 42
#endif
#define MAXN 10010
using namespace std;
struct Bigint
{
	int len, s[MAXN], symbol;
	Bigint()
	{
		memset(s, 0, sizeof(s));
		len = 1;
		symbol = 0;
	}
	inline Bigint operator = (const char*num)
	{
		Bigint();
		if (num[0] == '-')
		{
			symbol = 1;
			len = strlen(num) - 1;
			for (int i = 1; i <= len; ++i)
				s[i - 1] = num[len - i + 1] - '0';
		}
		else
		{
			symbol = 0;
			len = strlen(num);
			for (int i = 0; i < len; ++i)
				s[i] = num[len - i - 1] - '0';
		}
		return *this;
	}
	inline Bigint operator = (const int num)
	{
		char a[MAXN];
		if (num < 0)
		{
			sprintf(a, "%d", 0 - num);
			*this = a;
			symbol = 1;
		}
		else
		{
			sprintf(a, "%d", num);
			*this = a;
			symbol = 0;
		}
		return *this;
	}
	inline Bigint (const int num)
	{
		*this = num;
	}
	inline Bigint (const char * num)
	{
		*this = num;
	}
	inline Bigint operator = (const Bigint &a)
	{
		symbol = a.symbol;
		len = a.len;
		FOR(i, 0, len)
		s[i] = a.s[i];
		return *this;
	}
	inline int unsigned_cmp(const Bigint &a)
	{
		if (len > a.len)
			return 1;
		else if (len < a.len)
			return -1;
		else
		{
			//			cout<<1;
			for (int i = len - 1; i >= 0; i--)
			{
				if (s[i] > a.s[i])
					return 1;
				else if (s[i] < a.s[i])
					return -1;
			}
		}
		return 0;
	}
	inline int cmp (const Bigint &a)
	{
		if (a.symbol != symbol)
		{
			if (a.symbol == 1)
				return 1;
			else
				return -1;
		}
		else
		{
			if (symbol == 0)
				return unsigned_cmp(a);
			else
				return 0 - unsigned_cmp(a);
		}
	}
	inline bool operator > (const Bigint &a)
	{
		int tmp = cmp(a);
		if (tmp == 1)
			return true;
		else
			return false;
	}
	inline bool operator == (const Bigint &a)
	{
		int tmp = cmp(a);
		if (tmp == 0)
			return true;
		else
			return false;
	}
	inline bool operator < (const Bigint &a)
	{
		int tmp = cmp(a);
		if (tmp == -1)
			return true;
		else
			return false;
	}
	inline bool operator >= (const Bigint &a)
	{
		int tmp = cmp(a);
		if (tmp == 1 or tmp == 0)
			return true;
		else
			return false;
	}
	inline bool operator <= (const Bigint &a)
	{
		int tmp = cmp(a);
		if (tmp == -1 or tmp == 0)
			return true;
		else
			return false;
	}
	inline Bigint unsigned_plus (const Bigint &a)
	{
		Bigint c;
		c.len = max(len, a.len) + 1;
		for (int i = 0, x = 0; i < c.len; ++i)
		{
			c.s[i] = s[i] + a.s[i] + x;
			x = c.s[i] / 10;
			c.s[i] = c.s[i] % 10;
		}
		if (c.s[c.len - 1] == 0)
			--c.len;
		return c;
	}
	inline Bigint unsigned_minus (const Bigint &a)
	{
		Bigint c;
		c.len = max(len, a.len) + 1;
		for (int i = 0, x = 0; i < c.len; ++i)
		{
			c.s[i] = s[i] - a.s[i] - x;
			if (c.s[i] < 0)
				c.s[i] += 10, x = 1;
			else
				x = 0;
		}
		for (int i = c.len - 1; i >= 0; i--)
		{
			//			cout<<len<<" ";
			if (c.s[i] == 0)
				--c.len;
			else
				break;
		}
		return c;
	}
	inline Bigint operator + (Bigint &a)
	{
		if (symbol == a.symbol)
		{
			if (symbol == 0)
			{
				Bigint c = unsigned_plus(a);
				c.symbol = 0;
				return c;
			}
			else
			{
				Bigint c = unsigned_plus(a);
				c.symbol = 1;
				return c;
			}
		}
		else
		{
			if (symbol == 0)
			{
				if (unsigned_cmp(a) != -1)
				{
					Bigint c = unsigned_minus(a);
					c.symbol = 0;
					return c;
				}
				else
				{
					Bigint c = *this;
					c = a.unsigned_minus(c);
					c.symbol = 1;
					return c;
				}
			}
			else
			{
				if (unsigned_cmp(a) != -1)
				{
					Bigint c = unsigned_minus(a);
					c.symbol = 1;
					return c;
				}
				else
				{
					Bigint c = *this;
					c = a.unsigned_minus(c);
					c.symbol = 0;
					return c;
				}
			}
		}
	}
	inline Bigint operator - (Bigint &a)
	{
		if (symbol == a.symbol)
		{
			if (symbol == 0)
			{
				//				cout<<cmp(a);
				if (cmp(a) != -1)
				{
					Bigint tmp = unsigned_minus(a);
					tmp.symbol = 0;
					return tmp;
				}
				else
				{
					Bigint tmp = *this;
					tmp = a.unsigned_minus(tmp);
					tmp.symbol = 1;
					return tmp;
				}
			}
			else
			{
				if (unsigned_cmp(a) != -1)
				{
					Bigint tmp = unsigned_minus(a);
					tmp.symbol = 1;
					return tmp;
				}
				else
				{
					Bigint tmp = *this;
					tmp = a.unsigned_minus(tmp);
					tmp.symbol = 0;
					return tmp;
				}
			}
		}
		else
		{
			if (symbol == 0)
			{
				Bigint tmp = unsigned_plus(a);
				tmp.symbol = 0;
				return tmp;
			}
			else
			{
				Bigint tmp = unsigned_plus(a);
				tmp.symbol = 1;
				return tmp;
			}
		}
	}
	inline Bigint operator * (const Bigint &x)
	{
		Bigint c;
		c.len = len + x.len;
		for (int i = 0; i < len; ++i)
			for (int j = 0; j < x.len; ++j)
			{
				c.s[i + j] += s[i] * x.s[j];
				c.s[i + j + 1] += c.s[i + j] / 10;
				c.s[i + j] %= 10;
			}
		for (int i = c.len - 1; i >= 0; i--)
		{
			if (c.s[i] == 0)
				--c.len;
			else
				break;
		}
		c.symbol = (symbol != x.symbol);
		return c;
	}
	inline Bigint operator ^ (int x)
	{
		Bigint c = *this, ans = *this;
		for (; x != 1; x >>= 1)
		{
			ans = ans * c;
			if (x % 2 == 1)
				ans = ans * c;
			c = c * c;
		}
		return ans;
	}
	inline void operator += (Bigint &a)
	{
		*this = *this + a;
	}
	inline void operator -= (Bigint &a)
	{
		*this = *this - a;
	}
	inline void operator *= (const Bigint &a)
	{
		*this = *this * a;
	}
	inline void operator ^= (int &a)
	{
		*this = *this ^ a;
	}
};
ostream& operator<<(ostream &out, const Bigint& x)
{
	if (x.symbol == 1)
		printf("-");
	else if (x.len == 0)
		printf("0");
	for (int i = x.len - 1; i >= 0; --i)
		printf("%d", x.s[i]);
	return out;
}
istream& operator>>(istream &in, Bigint &x)
{
	char num[MAXN];
	in >> num;
	x = num;
	return in;
}