Doctor's Memorable Codes

Time Limit : 1 sec, Memory Limit : 65536 KB

博士の暗号

博 士 : ?D-C'KOPUA

ピーター : どうしたんですか、デビッド博士? わけのわからないことを叫ぶのにはもう慣れましたが、 今日は文章にすらなっていませんよ。

博 士 : ほれ。


ピーター : なんですか? この表は......ああ、予選の問題にこんなのがありました。表を使って文字を置き換え ると文字数が減るんですよね。まさか予選と本選で同じ問題を出して手を抜こうって気じゃないでし ょうね。

博 士 : 逆じゃよ。

ピーター : 逆? なるほど、今度は短くした文字列を元に戻そうって問題ですか。ということは「?D-C'KOPUA」の 文字を、この表を使って「文字」から「符号」に置きかえるんですね......できましたよ。

11111 00011 11101 00010 11110 01010 01110 01111 10100 00000

博 士 : うむ。次はこれじゃ。


ピーター : そうそう、こんな表もありましたね。これを逆に使うんだから「符号」から「文字」に置き換えればいい んですね。でも、最初は「11111」ですが表にありませんよ?

博 士 : そういうときは、もっと短くするか、後ろとつなげるかしてみるのだよ。

ピ ー タ ー : じゃあ短くして......あ、 「111」ならあります。じゃあ最初は「P」ですね。そうすると残りは「11」ですが、 これはぴったり合うのがないから次の「00011」から 1 文字借りて「110」にすればいいんですね。

博 士 : そうそう。つまり「E」だね。

ピ ー タ ー : それで残るのが「0011」なので、これも次から借りて「00111」にして「T」と......。全部できました。最 後の「0000」は捨てちゃえばいいんですよね?


博 士 : そうじゃ、よろしい。次はこれじゃ。

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

博 士 : さらにこれじゃ。

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

博 士 : 仕上げにこうじゃ。

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

ピ ー タ ー : しっかし面倒だなあ。博士、今度は自分でプログラムを作って下さいよ。

ということで、博士のかわりに、上の文章を置き換えるプログラムを作成してください。

Input

複数のデータセットが与えられます。各データセットとして、1つの文字列(表に含まれる文字からなる 200 文字以下の文字列)が1行に与えられます。入力の終わりまで処理してください。データセットの数は 200 を超えません。

Output

各データセットごとに、変換後の文字列を1行に出力してください。

Sample Input

?D-C'KOPUA

Output for the Sample Input

PETER POTTER

Source: PC Koshien 2005 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2005
(modified version)
http://www.pref.fukushima.jp/pc-concours/