File Compression

Time Limit: 1 Second    Memory Limit: 32768 KB

Much effort has been made to raise compression ratios. In recent years someone comes up with a method that rearranges the original file, so that they obtain higher compression ratio. It goes like this:

Original String, S: example

1) Make n string from S (n is the length of S). The ith string is made from i-1th string by shifting left one character.

example
xamplee
ampleex
mpleexa
pleexam
leexamp
eexampl

2) Sort these n strings by their initial characters. As to strings with the same initial characters, their original order is preserved.

ampleex
example
eexampl
leexamp
mpleexa
pleexam
xamplee

3) The rightmost characters form the target string.

Target String, S': xelpame

Now it is your task to implement the encoding and decoding process. Notice that you have to know the initial character of S to decode.

Input

This problem contains multiple tests. Each test starts with a word "encode" or "decode", followed by the string to be encoded or decoded. The string does not contain any space character. The length of the string will not exceed 100. The last character of the string to be decoded is the initial character of the original string and should not be countered in the target string itself.

Output

One line for each test, containing the encoded or decoded string.

Sample Input

encode example
decode xelpamee

Sample Output

xelpame
example

Submit

Source: ZOJ Monthly, December 2002