Doctor's Memorable Codes

Hiroshi:? D-C'KOPUA

Peter: What's wrong, Dr. David? I'm used to shouting something I don't understand, but I'm not even writing it today.

Hiroshi: Here.

Peter: What? This table ... oh, there was something like this in the qualifying question. Replacing characters using a table reduces the number of characters. I don't think I'm willing to give the same problem in the qualifying and the final and cut corners.

Hiroshi: It's the other way around.

Peter: Reverse? I see, is it a problem to get the shortened string back? That means that you can replace the letters "? D-C'KOPUA" from "letter" to "sign" using this table ...

11111 00011 11101 00010 11110 01010 01110 01111 10100 00000

Hiroshi: Umm. Next is this.

Peter: Yeah, there was also a table like this. Since this is used in reverse, you can replace "sign" with "character". But at first it is "11111", but it's not in the table, right?

Hiroshi: In that case, try making it shorter or connecting it to the back.

Peter: Then shorten it ... Oh, there is "111". Then it is "P" at first. Then, the rest is "11", but since this does not fit exactly, you can borrow one character from the next "00011" and make it "110".

Hiroshi: That's right. In other words, it's "E".

Peter: That's what remains of "0011", so I borrowed this from the next and changed it to "00111" and said "T" ... I've done it all. You should throw away the last "0000", right?

Hiroshi: That's right. Next is this.

? D-C'?-C'-LMGZN? FNJKN- WEYN? P'QMRWLPZLKKTPOVRGDI

Hiroshi: Furthermore, this is it.

? P'QNPY? IXX? IXXK.BI -G? R'RPP'RPOVWDMW? SWUVG'-LCMGQ

Hiroshi: Let's finish it.

? P'QMDUEQ GADKOQ? SWUVG'-LCMG? X? IGX, PUL.? UL.VNQQI

Peter: It's a hassle. Doctor, please make your own program this time.

So, instead of the doctor, create a program that replaces the above sentence.

Input

Given multiple datasets. For each dataset, one string (a string of 200 characters or less consisting of the characters contained in the table) is given on one line. Please process until the end of the input. The number of datasets does not exceed 200.

Output

For each data set, output the converted character string on one line.

Example

Input

?D-C'KOPUA

Output

PETER POTTER

inputFormat

Input

Given multiple datasets. For each dataset, one string (a string of 200 characters or less consisting of the characters contained in the table) is given on one line. Please process until the end of the input. The number of datasets does not exceed 200.

outputFormat

Output

For each data set, output the converted character string on one line.

Example

Input

?D-C'KOPUA

Output

PETER POTTER

样例

?D-C'KOPUA

PETER POTTER