#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 42;
map<char, int> to[maxn];
int len[maxn], link[maxn], cnt[maxn];
int last, sz = 1;
void add_letter(int &last, char c)
{
int p = last;
if(to[p][c])
{
int q = to[p][c];
if(len[q] == len[p] + 1)
{
last = q;
return;
}
int cl = sz++;
to[cl] = to[q];
link[cl] = link[q];
len[cl] = len[p] + 1;
link[q] = last = cl;
for(; to[p][c] == q; p = link[p])
to[p][c] = cl;
return;
}
last = sz++;
len[last] = len[p] + 1;
for(; to[p][c] == 0; p = link[p])
to[p][c] = last;
if(to[p][c] == last)
return;
int q = to[p][c];
if(len[q] == len[p] + 1)
{
link[last] = q;
return;
}
int cl = sz++;
to[cl] = to[q];
link[cl] = link[q];
len[cl] = len[p] + 1;
link[last] = link[q] = cl;
for(; to[p][c] == q; p = link[p])
to[p][c] = cl;
}
int main()
{
int last = 0;
for(int i = 0; i < 1e5; i++)
add_letter(last, 'a');
for(int i = last; i >= 0; i--)
add_letter(i, 'b');
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IG1heG4gPSAxZTYgKyA0MjsKbWFwPGNoYXIsIGludD4gdG9bbWF4bl07CmludCBsZW5bbWF4bl0sIGxpbmtbbWF4bl0sIGNudFttYXhuXTsKaW50IGxhc3QsIHN6ID0gMTsKCnZvaWQgYWRkX2xldHRlcihpbnQgJmxhc3QsIGNoYXIgYykKewoJaW50IHAgPSBsYXN0OwoJaWYodG9bcF1bY10pCgl7CgkJaW50IHEgPSB0b1twXVtjXTsKCQlpZihsZW5bcV0gPT0gbGVuW3BdICsgMSkKCQl7CgkJCWxhc3QgPSBxOwoJCQlyZXR1cm47CgkJfQoJCWludCBjbCA9IHN6Kys7CgkJdG9bY2xdID0gdG9bcV07CgkJbGlua1tjbF0gPSBsaW5rW3FdOwoJCWxlbltjbF0gPSBsZW5bcF0gKyAxOwoJCWxpbmtbcV0gPSBsYXN0ID0gY2w7CgkJZm9yKDsgdG9bcF1bY10gPT0gcTsgcCA9IGxpbmtbcF0pCgkJCXRvW3BdW2NdID0gY2w7CgkJcmV0dXJuOwoJfQoJbGFzdCA9IHN6Kys7CglsZW5bbGFzdF0gPSBsZW5bcF0gKyAxOwoJZm9yKDsgdG9bcF1bY10gPT0gMDsgcCA9IGxpbmtbcF0pCgkJdG9bcF1bY10gPSBsYXN0OwoJaWYodG9bcF1bY10gPT0gbGFzdCkKCQlyZXR1cm47CglpbnQgcSA9IHRvW3BdW2NdOwoJaWYobGVuW3FdID09IGxlbltwXSArIDEpCgl7CgkJbGlua1tsYXN0XSA9IHE7CgkJcmV0dXJuOwoJfQoJaW50IGNsID0gc3orKzsKCXRvW2NsXSA9IHRvW3FdOwoJbGlua1tjbF0gPSBsaW5rW3FdOwoJbGVuW2NsXSA9IGxlbltwXSArIDE7CglsaW5rW2xhc3RdID0gbGlua1txXSA9IGNsOwoJZm9yKDsgdG9bcF1bY10gPT0gcTsgcCA9IGxpbmtbcF0pCgkJdG9bcF1bY10gPSBjbDsKfQoKaW50IG1haW4oKQp7CiAgICBpbnQgbGFzdCA9IDA7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgMWU1OyBpKyspCiAgICAgICAgYWRkX2xldHRlcihsYXN0LCAnYScpOwogICAgZm9yKGludCBpID0gbGFzdDsgaSA+PSAwOyBpLS0pCiAgICAgICAgYWRkX2xldHRlcihpLCAnYicpOwp9Cg==