//Это mlg проект он заходит с первого раза (нет)
//#include <mlg>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<math.h>
#include<algorithm>
#include<time.h>
#include<stdio.h>
#include<stack>
#include<queue>
#include<deque>
#include<fstream>

using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define s() size()

const long long mod = 1e9;

vector<long long> summ(vector<long long> a, vector<long long> b)
{
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	vector<long long> c;
	for (long long i = 0; i < max(a.size(), b.size()); i++)
	{
		long long q = 0;
		if (i < a.size())
			q += a[i];
		if (i < b.size())
			q += b[i];
		if (c.size() <= i)
			c.push_back(q);
		else
			c[i] += q;
		if (c[i] >= mod)
		{
			long long h = c[i];
			for (long long i = 0; i < 9; i++)
				h /= 10;
			if (c.size() <= i + 1)
				c.push_back(h);
			else
				c[i + 1] += h;
			c[i] %= mod;
		}
	}
	reverse(c.begin(), c.end());
	return c;
}

vector<long long> umn(vector<long long> a, vector<long long> b)
{
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	vector<long long> c;
	for (long long i = 0; i < a.size(); i++)
	{
		for (long long j = 0; j < b.size(); j++)
		{
			if (c.size() <= i + j)
				c.push_back(0);
			c[i + j] += a[i] * b[j];
			if (c[i + j] >= mod)
			{
				long long h = c[i + j];
				for (long long i = 0; i < 9; i++)
					h /= 10;
				if (c.size() <= i + j + 1)
					c.push_back(h);
				else
					c[i + j + 1] += h;
					c[i + j] %= mod;
			}
		}
	}
	reverse(c.begin(), c.end());
	return c;
}


vector<long long> nsumm(vector<long long> a, vector<long long> b)
{
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	vector<long long> c; c.resize(a.size());
	for (long long i = 0; i < a.size(); i++)
	{
		if (i + 1 < a.size() && c[i] < 0)
		{
			c[i] += mod;
			c[i + 1]--;
		}
		long long q = 0;
		if (i < a.size())
			q += a[i];
		if (i < b.size())
		{
			if (q < b[i] && i + 1 < a.size())
			{
				c[i + 1]--;
				q += mod;
			}
			q -= b[i];
		}
		c[i] += q;
		if (c[i] >= mod)
		{
			long long h = c[i];
			for (long long i = 0; i < 9; i++)
				h /= 10;
			if (c.size() <= i + 1)
				c.push_back(h);
			else
				c[i + 1] += h;
			c[i] %= mod;
		}
	}
	reverse(c.begin(), c.end());
	return c;
}

long long func(vector<long long> a)
{
	long long q = 0;
	for (long long i = a.size() - 1; i >= 0; i--)
		q = q * 10 + a[i] - '0';
	return q;
}

vector<long long> inp(string a)
{
	vector<long long> b;
	vector<long long> u;
	reverse(a.begin(), a.end());
	for (long long i = 0; i < a.size(); i++)
	{
		u.push_back(a[i]);
		if (i % 9 == 8)
		{
			b.push_back(func(u));
			u.clear();
		}
	}
	if (u.size() != 0)
		b.push_back(func(u));
	reverse(b.begin(), b.end());
	return b;
}

void oup(vector<long long> a)
{
	vector<long long> p;
	long long i = 0;
	while (i + 1 < a.size() && a[i] == 0)
		i++;
	p.push_back(a[i]); i++;
	for (; i < a.size(); i++)
	{
		long long t = 1e8;
		while (a[i] < t)
		{
			p.push_back(1);
			t /= 10;
		}
		if (a[i] != 0)
			p.push_back(a[i]);
	}
	for (int i = 0; i < p.size(); i++)
	{
		long long q = p[i];
		if (q == 0)
			return;
		while (q != 0)
		{
			if (q % 10 != 1 && q % 10 != 2)
				return;
			q /= 10;
		}
	}
	exit(0);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

}