1051 P,MTHBGWB

原文

時間制限:1000ミリ秒
メモリ制限:10000KB

P,MTHBGWB

問題

モールス信号は文字を可変長のドットとダッシュの列で表現する。実際の利用では、各文字は短い休止によって区切られる。以下の表はモールス信号の対応表である:

以下に示す4つのドットとダッシュの列は未定義であることに注意すること。ここでは以下のように定義する。(これらは実際のモールス信号ではない。)

ここで、"ACM_GREATER_NY_REGION"というメッセージは以下のようにエンコードされる:
.- -.-. -- ..-- --. .-. . .- - . .-. ..-- -. -.-- ..-- .-. . --. .. --- -.
M.E.Ohaverは区切られたモールス信号をベースにして、ある符号化方式を提案した。彼女の方式では、文字間の休止(モールス信号は接頭辞が必要である)を、ドットとダッシュの個数を示す数字の列に置き替えている。例えば、".--.-.--"というメッセージを考えよう。どこに休止があるかを知らなければ、これは"ACM","ANK",または他のいくつかの可能性をもっている。しかし、もしこれに長さの情報を付加したならば、".--.-.--242"は1通りに決まる。

Ohaverの方法は、符号化も解読も以下の方法で行われる。
1. テキストを、休止がない代わりに長さをあらわす数字の列がついたモールス信号に変換する。
2. 数字の列を逆転する。
3. モールス信号を1と逆の方法で復元する。
例えば、符号化されたメッセージ"AKADTOF_IBOETATUK_IJN"を考えてみよう。長さ文字列つきのモールス信号に変換すると、".--.-.--..----..-...--..-...---.-.--..--.-..--...----.232313442431121334242"となる。数字を逆転させてオリジナルメッセージを復元すると、"ACM_GREATER_NY_REGION"となる。

入力

この問題はOhaverの符号化アルゴリズムを実装しなければならない。入力はOhaverのアルゴリズムによって符号化されたいくつかもメッセージからなる。入力の最初の行はテストケースの数を表す整数nからなる。続くn行は1行に1つのメッセージが書かれている。各メッセージは26の大文字の英文字とアンダースコア、コンマ、ピリオド、そして疑問符のみからなる。メッセージの長さは100文字を超えることはない。

出力

各入力メッセージに対して、1から始まる行番号、コロン、スペース、そして復元されたメッセージを出力しなさい。出力フォーマットは空白についても厳密に扱われる。

入力例

5
AKADTOF_IBOETATUK_IJN
PUEL
QEWOISE.EIVCAEFNRXTBELYTGD.
?EJHUT.TSMYGW?EJHOT
DSU.XFNCJEVE.OE_UJDXNO_YHU?VIDWDHPDJIKXZT?E

出力例

1: ACM_GREATER_NY_REGION
2: PERL
3: QUOTH_THE_RAVEN,_NEVERMORE.
4: TO_BE_OR_NOT_TO_BE?
5: THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG

出典

Greater New York 2001