for(t=[j=0];s=readline();j++)for(i in s)c=s[i],u=t[i]||'',t[i++]=c>'{'?c+u:u+c for(a=++i;++a