#include<deque>#include<queue>#include<list>#include<vector>#include<iostream>#include<queue>#include<cstdio>#include<cctype>#include<string.h> #include<map>#include<algorithm>#include<stdlib.h>using namespace std;enum { SIZ = 108, ALP = 256,};int num;int next[ALP]; int ptr[SIZ]; char str[SIZ]; char out[SIZ];void enpre(){ int v, i, t; for(i=num-1; i>=0; i--){ v = str[i]; ptr[i] = next[v]; next[v] = i; } for(i=0, t=0; i<ALP; i++){ for(v=next[i]; v>=0; v = ptr[v]){ out[t++] = v==0?str[num-1]:str[v-1]; } } out[t] = 0; printf("%sn", out);}void depre(){ int v, i, t; out[0] = str[--num]; out[num] = str[num] = 0; for(i=0; i<num; i++){ v = str[i]; ptr[i] = next[v]; next[v] = i; } static int tail[ALP]; static int head[ALP]; t = 0; for(i=0; i<ALP; i++){ head[i] = t; for(v=next[i]; v>=0; v=ptr[v]){ t++; } tail[i] = t-1; } for(i=num-1; i>0; i--){ t = i==num-1?0:i+1; t = out[t]; if(i == num-1){ out[i] = str[head[t]++]; } else { out[i] = str[tail[t]--]; } } printf("%sn", out);}void fun(){ char c = str[0]; scanf("%s", str); num = (int)strlen(str); memset(next, -1, sizeof(next)); if(c == 'e'){ enpre(); } else {depre(); }}int main(){ while( scanf("%s", str) > 0){ fun(); }return 0;}
