#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
#define isnum(a) (a>=48 && a<=57)
#define isS(a) (a>='a' && a<='z')
#define isU(a) (a>='A' && a<='Z')
#define toS(a) (isU(a)?a+32:a)
#define toU(a) (isS(a)?a-32:a)
#define toC(a) a&15
inline lli get(){
lli y, s = 1, i = 10;
y = 0;
char c = getchar();
while (!isnum(c)){
if (c == '-')s = -1; c = getchar();
}
while (isnum(c))y = (y << 1) + (y << 3) + (toC(c)), c = getchar();
if (c != '.')return y*s;
c = getchar();
while (isnum(c))y = y + (toC(c)) / i, i = (i << 1) + (i << 3), c = getchar();
return y*s;
}
inline void put(int x)
{
if (!x){ putchar('0'); return; }
char ch[21];
int ln = 0;
while (x){
ch[ln++] = x % 10;
x /= 10;
}
ln--;
while (ln >= 0){ putchar(ch[ln--] + 48); }
}
int main() {
// your code goes here
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIGxvbmcgbG9uZyBsbGk7CiNkZWZpbmUgaXNudW0oYSkgKGE+PTQ4ICYmIGE8PTU3KQojZGVmaW5lIGlzUyhhKSAoYT49J2EnICYmIGE8PSd6JykKI2RlZmluZSBpc1UoYSkgKGE+PSdBJyAmJiBhPD0nWicpCiNkZWZpbmUgdG9TKGEpIChpc1UoYSk/YSszMjphKQojZGVmaW5lIHRvVShhKSAoaXNTKGEpP2EtMzI6YSkKI2RlZmluZSB0b0MoYSkgYSYxNQoKaW5saW5lIGxsaSBnZXQoKXsKICAgIGxsaSB5LCBzID0gMSwgaSA9IDEwOwogICAgeSA9IDA7CiAgICBjaGFyIGMgPSBnZXRjaGFyKCk7CiAgICB3aGlsZSAoIWlzbnVtKGMpKXsKICAgICAgICBpZiAoYyA9PSAnLScpcyA9IC0xOyBjID0gZ2V0Y2hhcigpOwogICAgfQogICAgd2hpbGUgKGlzbnVtKGMpKXkgPSAoeSA8PCAxKSArICh5IDw8IDMpICsgKHRvQyhjKSksIGMgPSBnZXRjaGFyKCk7CiAgICBpZiAoYyAhPSAnLicpcmV0dXJuIHkqczsKICAgIGMgPSBnZXRjaGFyKCk7CiAgICB3aGlsZSAoaXNudW0oYykpeSA9IHkgKyAodG9DKGMpKSAvIGksIGkgPSAoaSA8PCAxKSArIChpIDw8IDMpLCBjID0gZ2V0Y2hhcigpOwogICAgcmV0dXJuIHkqczsKfQoKaW5saW5lIHZvaWQgcHV0KGludCB4KQp7CiAgICBpZiAoIXgpeyBwdXRjaGFyKCcwJyk7IHJldHVybjsgfQogICAgY2hhciBjaFsyMV07CiAgICBpbnQgbG4gPSAwOwogICAgd2hpbGUgKHgpewogICAgICAgIGNoW2xuKytdID0geCAlIDEwOwogICAgICAgIHggLz0gMTA7CiAgICB9CiAgICBsbi0tOwogICAgd2hpbGUgKGxuID49IDApeyBwdXRjaGFyKGNoW2xuLS1dICsgNDgpOyB9Cn0KCgppbnQgbWFpbigpIHsKCS8vIHlvdXIgY29kZSBnb2VzIGhlcmUKCXJldHVybiAwOwp9