n,m[99999]; // first rule
c,r[99999][2]; // other rules all have two symbols
i,s,t;
main(){
for(s=0;s<n-1;s++) {
for(t=s+2;t<n-1;t++)if(m[s]==m[t]&&m[s+1]==m[t+1]){
// create new rule
r[c][0]=m[s];
r[c++][1]=m[s+1];
// replace
for(i=t=s;i<n-1;i++){
if(m[i]==r[c-1][0]&&m[i+1]==r[c-1][1]){
m[t++]=-c;
i++;
}else
m[t++]=m[i];
}
n=t;
}
}
for(s=-1;s<c;s++){
for(t=0;t<(s<0?n:2);t++){
i=(s<0?m:r[s])[t];
}
}
}
bixtWzk5OTk5XTsgLy8gZmlyc3QgcnVsZQpjLHJbOTk5OTldWzJdOyAvLyBvdGhlciBydWxlcyBhbGwgaGF2ZSB0d28gc3ltYm9scwoKaSxzLHQ7CgptYWluKCl7CiAgICBmb3IoOyhtW25dPWdldGNoYXIoKSk+MDtuKyspOwoKICAgIGZvcihzPTA7czxuLTE7cysrKSB7CiAgICAgICAgZm9yKHQ9cysyO3Q8bi0xO3QrKylpZihtW3NdPT1tW3RdJiZtW3MrMV09PW1bdCsxXSl7CiAgICAgICAgICAgIC8vIGNyZWF0ZSBuZXcgcnVsZQogICAgICAgICAgICByW2NdWzBdPW1bc107CiAgICAgICAgICAgIHJbYysrXVsxXT1tW3MrMV07CiAgICAgICAgICAgIC8vIHJlcGxhY2UKICAgICAgICAgICAgZm9yKGk9dD1zO2k8bi0xO2krKyl7CiAgICAgICAgICAgICAgICBpZihtW2ldPT1yW2MtMV1bMF0mJm1baSsxXT09cltjLTFdWzFdKXsKICAgICAgICAgICAgICAgICAgICBtW3QrK109LWM7CiAgICAgICAgICAgICAgICAgICAgaSsrOwogICAgICAgICAgICAgICAgfWVsc2UKICAgICAgICAgICAgICAgICAgICBtW3QrK109bVtpXTsKICAgICAgICAgICAgfQogICAgICAgICAgICBuPXQ7CgogICAgICAgIH0KICAgIH0KCiAgICBmb3Iocz0tMTtzPGM7cysrKXsKICAgICAgICBwcmludGYoIiVkPSIscysxMSk7CiAgICAgICAgZm9yKHQ9MDt0PChzPDA/bjoyKTt0KyspewogICAgICAgICAgICBpPShzPDA/bTpyW3NdKVt0XTsKICAgICAgICAgICAgaTwwP3ByaW50ZigiJWQgIiwxMC1pKTpwcmludGYoIiVjICIsaSk7CiAgICAgICAgfQogICAgICAgIHByaW50ZigiXG4iKTsKICAgIH0KCn0=