/*
NISHANT GUPTA
CSE-MNNIT ALLAHABAD
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#include <cctype>
#include <utility>
#include <map>
#include <string>
#include <climits>
#include <set>
#include <string>
#include <sstream>
#include <utility>
#include <ctime>
#include <cassert>
#include <fstream>
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> II;
typedef vector<long long> VLL;
typedef vector<bool> VB;
#define SZ(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define MS(A) memset(A, 0, sizeof(A))
#define MSV(A,a) memset(A, a, sizeof(A))
#define MAX(a,b) ((a >= b) ? (a) : (b))
#define MIN(a,b) ((a >= b) ? (b) : (a))
#define ABS(a) (((a) > 0) ? (a) : (-a))
#define MP make_pair
#define X first
#define Y second
#define PB push_back
#define FOUND(A, x) (A.find(x) != A.end())
#define getcx getchar_unlocked
#define INF 0x3f3f3f3f
#define INFL (LL(1e18))
#define EPS 1e-12
#define chkbit(s, b) (s & (1<<b))
#define setbit(s, b) (s |= (1<<b))
#define clrbit(s, b) (s &= ~(1<<b))
#define rep(i, a, n) for(i = a; i < n; i++)
#define rev(i, a, n) for(i = a; i > n; i--)
#define FORALL(itr, c) for(itr = (c).begin(); itr != (c).end(); itr++)
#define ALL(A) A.begin(), A.end()
#define LLA(A) A.rbegin(), A.rend()
inline void inp( int &n )
{
n=0; int ch=getcx();int sign=1;
while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getcx();}
while( ch >= '0' && ch <= '9' )
n = (n<<3)+(n<<1) + ch-'0', ch=getcx();
n=n*sign;
}
inline void inp1( LL &n )
{
n=0; LL ch=getcx();LL sign=1;
while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getcx();}
while( ch >= '0' && ch <= '9' )
n = (n<<3)+(n<<1) + ch-'0', ch=getcx();
n=n*sign;
}
int main()
{
}
LyoKCU5JU0hBTlQgR1VQVEEKCUNTRS1NTk5JVCBBTExBSEFCQUQKKi8KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0ZGlvPgojaW5jbHVkZSA8Y3N0ZGxpYj4KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxjc3RyaW5nPgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDxjY3R5cGU+CiNpbmNsdWRlIDx1dGlsaXR5PgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8Y2xpbWl0cz4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHNzdHJlYW0+CiNpbmNsdWRlIDx1dGlsaXR5PgojaW5jbHVkZSA8Y3RpbWU+CiNpbmNsdWRlIDxjYXNzZXJ0PgojaW5jbHVkZSA8ZnN0cmVhbT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiBsb25nIGxvbmcgTEw7CnR5cGVkZWYgdmVjdG9yPGludD4gVkk7CnR5cGVkZWYgcGFpcjxpbnQsIGludD4gSUk7CnR5cGVkZWYgdmVjdG9yPGxvbmcgbG9uZz4gVkxMOwp0eXBlZGVmIHZlY3Rvcjxib29sPiBWQjsgCiNkZWZpbmUgU1ooQSkgKChpbnQpQS5zaXplKCkpCiNkZWZpbmUgTEVOKEEpICgoaW50KUEubGVuZ3RoKCkpCiNkZWZpbmUgTVMoQSkgbWVtc2V0KEEsIDAsIHNpemVvZihBKSkKI2RlZmluZSBNU1YoQSxhKSBtZW1zZXQoQSwgYSwgc2l6ZW9mKEEpKQojZGVmaW5lIE1BWChhLGIpICgoYSA+PSBiKSA/IChhKSA6IChiKSkKI2RlZmluZSBNSU4oYSxiKSAoKGEgPj0gYikgPyAoYikgOiAoYSkpCiNkZWZpbmUgQUJTKGEpICgoKGEpID4gMCkgPyAoYSkgOiAoLWEpKQojZGVmaW5lIE1QIG1ha2VfcGFpcgojZGVmaW5lIFggZmlyc3QKI2RlZmluZSBZIHNlY29uZAojZGVmaW5lIFBCIHB1c2hfYmFjawojZGVmaW5lIEZPVU5EKEEsIHgpIChBLmZpbmQoeCkgIT0gQS5lbmQoKSkKI2RlZmluZSBnZXRjeCBnZXRjaGFyX3VubG9ja2VkCiNkZWZpbmUgSU5GIDB4M2YzZjNmM2YKI2RlZmluZSBJTkZMIChMTCgxZTE4KSkKI2RlZmluZSBFUFMgMWUtMTIgCiNkZWZpbmUgY2hrYml0KHMsIGIpIChzICYgKDE8PGIpKQojZGVmaW5lIHNldGJpdChzLCBiKSAocyB8PSAoMTw8YikpCiNkZWZpbmUgY2xyYml0KHMsIGIpIChzICY9IH4oMTw8YikpCiNkZWZpbmUgcmVwKGksIGEsIG4pIGZvcihpID0gYTsgaSA8IG47IGkrKykKI2RlZmluZSByZXYoaSwgYSwgbikgZm9yKGkgPSBhOyBpID4gbjsgaS0tKQojZGVmaW5lIEZPUkFMTChpdHIsIGMpIGZvcihpdHIgPSAoYykuYmVnaW4oKTsgaXRyICE9IChjKS5lbmQoKTsgaXRyKyspCiNkZWZpbmUgQUxMKEEpIEEuYmVnaW4oKSwgQS5lbmQoKQojZGVmaW5lIExMQShBKSBBLnJiZWdpbigpLCBBLnJlbmQoKQppbmxpbmUgdm9pZCBpbnAoIGludCAmbiApCnsgCgluPTA7ICAgIGludCBjaD1nZXRjeCgpO2ludCBzaWduPTE7ICAgCgl3aGlsZSggY2ggPCAnMCcgfHwgY2ggPiAnOScgKXtpZihjaD09Jy0nKXNpZ249LTE7IGNoPWdldGN4KCk7fSAKCXdoaWxlKCAgY2ggPj0gJzAnICYmIGNoIDw9ICc5JyApICAgIAoJbiA9IChuPDwzKSsobjw8MSkgKyBjaC0nMCcsIGNoPWdldGN4KCk7CgluPW4qc2lnbjsKfSAgIAkKaW5saW5lIHZvaWQgaW5wMSggTEwgJm4gKQp7IAoJbj0wOyAgICBMTCBjaD1nZXRjeCgpO0xMIHNpZ249MTsgICAKCXdoaWxlKCBjaCA8ICcwJyB8fCBjaCA+ICc5JyApe2lmKGNoPT0nLScpc2lnbj0tMTsgY2g9Z2V0Y3goKTt9IAoJd2hpbGUoICBjaCA+PSAnMCcgJiYgY2ggPD0gJzknICkgICAgCgluID0gKG48PDMpKyhuPDwxKSArIGNoLScwJywgY2g9Z2V0Y3goKTsKCW49bipzaWduOwp9ICAgCQoKaW50IG1haW4oKQp7CgkKfQ==