#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <set>

#include <climits>
#include <utility>

#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>

#include <cstring>
#include <cstdlib>
#include <cmath>

#define bazaNum 10
#define ll long long
#define Ld long double
#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

vector <int> vctPrime;

class MyInt
{
private:
public:
	vector <int> numar;

	MyInt();
	MyInt(ll nr);
	void fix();
	const int& operator [] (const int nr) const;
	void operator += (const MyInt &termen);
	void operator -= (const MyInt &scazator);
	void operator *= (const MyInt &factor);
	void operator /= (const MyInt &imp);
	MyInt operator + (const MyInt &term);
	MyInt operator - (const MyInt &scazator);
	MyInt operator * (const MyInt &factor);
	MyInt operator / (const MyInt &imp);
	friend ostream& operator << (ostream &out, const MyInt &vec);
	friend istream& operator >> (istream &cin, MyInt &vec);
	bool operator == (const MyInt &nr);
	bool operator != (const MyInt &nr);
	bool operator < (const MyInt &nr);
	bool operator <= (const MyInt &nr);
	bool operator > (const MyInt &nr);
	bool operator >= (const MyInt &nr);
};
MyInt putere(MyInt numar, ll exponent);
inline ll putere(ll numar, ll exponent, ll restRez);
inline int testPrim(int numar);
inline ll invers(ll x);
inline MyInt invers(MyInt x);
inline void prime(int LIM);
inline ll gcd(ll a, ll b);

MyInt :: MyInt()
{
	numar.resize(5);
	numar[0] = 1;
}

MyInt :: MyInt(ll nr)
{
	numar.resize(22);
	for (numar[0] = 1; nr; nr /= 10, numar[0]++)
		numar[numar[0]] = nr % 10;
	this->fix();
}

void MyInt :: fix()
{
	for (numar[0] = numar.size() - 1; numar[0] > 1 && !numar[numar[0]]; numar[0]--);
	numar.resize(numar[0] + 2);
}

const int& MyInt :: operator [] (const int nr) const
{
	return numar[nr];
}

void MyInt :: operator += (const MyInt &term)
{
	int nrTemp = 0, i;
	MyInt termen = term, sum;

	termen.numar.resize(max(numar[0], termen[0]) + 3);
	numar.resize(max(numar[0], termen[0]) + 3);
	sum.numar = numar;

	for (i = 1; i <= max(numar[0], termen[0]) || nrTemp; nrTemp /= bazaNum, i++)
		sum.numar[i] = (nrTemp = nrTemp + sum.numar[i] + termen[i]) % bazaNum;

	sum.fix();
	numar = sum.numar;
}

void MyInt :: operator -= (const MyInt &scazator)
{
	MyInt dif;
	int i, nrTemp = 0;

	dif.numar = numar;

	for (i = 1; i <= numar[0]; i++)
		dif.numar[i] += (nrTemp = (dif.numar[i] -= scazator[i] + nrTemp) < 0) * bazaNum;
	
	dif.fix();
	numar = dif.numar;
}

void MyInt :: operator *= (const MyInt &factor)
{
	MyInt prod;
	prod.numar.resize(numar[0] + factor[0] + 3);
	int i, j, t;

	for (i = 1; i <= numar[0]; i++)
		for (t = 0, j = 1; j <= factor[0] || t; j++, t /= bazaNum)
			prod.numar[i + j - 1] = (t += prod[i + j - 1] + numar[i] * factor[j]) % bazaNum;

	prod.fix();
	numar = prod.numar;
}

void MyInt :: operator /= (const MyInt &imp)
{
	MyInt cat;
}

MyInt MyInt :: operator + (const MyInt &term)
{
	int nrTemp = 0, i;
	MyInt sum, termen = term;

	termen.numar.resize(max(numar[0], termen[0]) + 3);
	numar.resize(max(numar[0], termen[0]) + 3);
	sum.numar = numar;

	for (i = 1; i <= max(numar[0], termen[0]) || nrTemp; nrTemp /= bazaNum, i++)
		sum.numar[i] = (nrTemp = nrTemp + numar[i] + termen[i]) % bazaNum;
	
	sum.fix();
	return sum;
}

MyInt MyInt :: operator - (const MyInt &scazator)
{
	MyInt dif;
	dif.numar.resize(numar[0] + 3);
	int i, nrTemp = 0;

	for (i = 1; i <= dif[0]; i++)
		dif.numar[i] += (nrTemp = (dif.numar[i] -= scazator[i] + nrTemp) < 0) * bazaNum;
	
	dif.fix();
	return dif;
}

MyInt MyInt :: operator * (const MyInt &factor)
{
	MyInt prod;
	prod.numar.resize(numar[0] + factor[0] + 3);
	int i, j, t;

	for (i = 1; i <= numar[0]; i++)
		for (t = 0, j = 1; j <= factor[0] || t; j++, t /= bazaNum)
			prod.numar[i + j - 1] = (t += prod[i + j - 1] + numar[i] * factor[j]) % bazaNum;
	
	prod.fix();
	return prod;
}

MyInt MyInt :: operator / (const MyInt &imp)
{
	MyInt cat;

	return cat;
}

ostream& operator << (ostream &cout, const MyInt &vec)
{
	for (int i = vec[0]; i; i--)
		cout << vec[i];
	cout << '\n';

    return cout;
}

istream& operator >> (istream &cin, MyInt &vec)
{
	string buffIn;
	cin >> buffIn;
	vec.numar.resize(buffIn.size() + 2);

	for (int i = 0; i < (int) buffIn.size(); i++)
		vec.numar[vec.numar[0]++] = buffIn[i] - '0';
	reverse(vec.numar.begin() + 1, vec.numar.begin() + vec.numar[0]);

	vec.fix();
	return cin;
}

bool MyInt :: operator == (const MyInt &nr)
{
	if (numar[0] != nr.numar[0])
		return 0;
	for (int i = 1; i <= numar[0]; i++)
		if (numar[i] != nr.numar[i])
			return 0;
	return 1;
}

bool MyInt :: operator != (const MyInt &nr)
{
	return !((*this) == nr);
}

bool MyInt :: operator > (const MyInt &nr)
{
	if (numar[0] > nr.numar[0])
		return 1;
	for (int i = numar[0]; i; i--)
		if (numar[i] > nr.numar[i])
			return 1;
		else if (numar[i] < nr.numar[0])
			return 0;
	return 0;
}

bool MyInt :: operator >= (const MyInt &nr)
{
	if ((*this) == nr || (*this) > nr)
		return 1;
	return 0;
}

bool MyInt :: operator < (const MyInt &nr)
{
	return !((*this) >= nr);
}

bool MyInt :: operator <= (const MyInt &nr)
{
	return !((*this) > nr);
}

MyInt putere(MyInt numar, int exponent)
{
	MyInt rest = MyInt(1);

	for (; exponent > 1; exponent /= 2)
	{
		if (exponent & 1)
			rest *= numar;

		numar *= numar;
	}

	return numar * rest;
}

inline ll putere(ll numar, int exponent, ll restRez)
{
	ll rest = 1;

	for (; exponent > 1; exponent /= 2)
	{
		if (exponent & 1)
			rest = (rest * numar) % restRez;

		numar = (numar * numar) % restRez;
	}

	return (numar * rest) % restRez;
}

inline MyInt sqrt(MyInt x)
{
}

inline int testPrim(int numar)
{
	int bazaPrim[3] = {2, 3, 61};

	if (numar == 1)
		return 0;

	for (int i = 0; i < 3; i++)
		if (bazaPrim[i] == numar)
			return 1;

	int ok = 0;
	for (int i = 0; i < 3; i++)
	{
		int ramas = numar - 1, verif = 0, put2 = 0;

		for (; !(ramas & 1); put2++, ramas >>= 1);

		ll x = putere(bazaPrim[i], ramas, numar);

		if (x == 1)
			verif = 1;
		for (put2++; put2 && !verif; put2--)
		{
			if (x == numar - 1)
				verif++;
			x = (x * x) % numar;
		}
		ok += verif;
	}

	return (ok / 3);
}

inline ll invers(ll x)
{
	ll rez = 0;
	for (; x; rez = rez * 10 + x % 10, x /= 10);

	return rez;
}

inline MyInt invers(MyInt x)
{
	reverse(x.numar.begin() + 1, x.numar.begin() + x.numar[0] + 1);

	x.fix();

	return x;
}

inline void prime(int LIM)
{
	vector <int> p(10000000);
	for (int i = 1; ((i * i) << 1) + (i << 1) <= LIM; i++)
		if (!(p[i >> 3] & (1 << (i & 7))))
			for (int j = ((i * i) << 1) + (i << 1); (j << 1) + 1 <= LIM; j += (i << 1) + 1)
				p[j >> 3] |= (1 << (j & 7));

	vctPrime.pb(2);
	for (int i = 1; (i << 1) + 1 <= LIM; i++)
		if (!(p[i >> 3] & (1 << (i & 7))))
			vctPrime.pb((i << 1) + 1);
}

inline ll gcd(ll a, ll b)
{
	if (b)
		return gcd(b, a % b);
	return a;
}

inline Ld areaTr(double x1, double y1, double x2, double y2, double x3, double y3)
{
	return (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2;
}