Under construction

Still being built. Things may change

False Sense of Security

Time limit2sMemory limit128 MB

Summary
Decode each line by turning it into pause-free Morse code, reversing the per-character length digits, and re-splitting the code into text.
Level

Easy3 of 10

Topics
String, Simulation, Hash map
Solved
No attempts yet

Problem

Freddy found a new way to grow much bigger cauliflowers. He wants to hand the method to his fellow gardener Tommy without letting anyone else steal it, so the two of them agreed on a simple encryption technique proposed by M. E. Ohaver.

The technique is built on Morse code, which writes every character as a sequence of dots and dashes whose length varies from character to character. These are the sequences for the twenty-six capital letters.

LetterCodeLetterCodeLetterCodeLetterCode
A.-H....O---V...-
B-...I..P.--.W.--
C-.-.J.---Q--.-X-..-
D-..K-.-R.-.Y-.--
E.L.-..S...Z--..
F..-.M--T-
G--.N-.U..-

Sixteen combinations of dots and dashes have length four, and real Morse code leaves four of them unused. This problem gives those four the characters below. They are not the assignments of real Morse code.

CharacterCode
_ underscore..--
, comma.-.-
. period---.
? question mark----

A short pause separates the characters of a message and is normally written as a space, so the text ACM_GREATER_NY_REGION goes out as

.- -.-. -- ..-- --. .-. . .- - . .-. ..-- -. -.-- ..-- .-. . --. .. --- -.

Ohaver's scheme mutilates Morse code by deleting the pauses between characters. The pauses carry real information, because Morse code has no fixed length and is not prefix free. Read .--.-.-- with the pauses gone and 108 different texts fit it, among them ACM, AKW, and ANY. The scheme therefore keeps a string of digits beside the dots and dashes, one digit per character, holding the length of that character's code. Written as .--.-.-- 242, the message is unambiguous again.

Encryption and decryption run the same three steps.

  1. Convert the text to Morse code with the pauses removed, and build the string of digits that records the code lengths.
  2. Reverse the string of digits.
  3. Cut the dots and dashes with the reversed digits as code lengths and turn each piece back into a character.

Run the steps on the encrypted message AKADTOF_IBOETATUK_IJN. Step 1 produces

.--.-.--..----..-...--..-...---.-.--..--.-..--...----. 232313442431121334242

Step 2 reverses the digits.

242433121134244313232

Cutting the same dots and dashes with those lengths gives back ACM_GREATER_NY_REGION.

The scheme is not very secure, but Freddy is satisfied with it. Write the program that runs it for him.

Input

The input holds several messages encrypted with Ohaver's algorithm, one message per line. Each message uses only the twenty-six capital letters, the underscore, the comma, the period, and the question mark. No message is longer than 1000 characters. The input ends at end of file.

Output

For each message in the input, print the decrypted message on one line.

Examples1

  1. Example 1

    Input
    FENDSVTSLHW.EDATS,EULAY
TRDNWPLOEF
NTTTGAZEJUIIGDUZEHKUE
QEWOISE.EIVCAEFNRXTBELYTGD.
?EJHUT.TSMYGW?EJHOT
DSU.XFNCJEVE.OE_UJDXNO_YHU?VIDWDHPDJIKXZT?E
ADAWEKHZN,OTEATWRZMZN_IDWCZGTEPION
    Expected output
    FALSE_SENSE_OF_SECURITY
CTU_PRAGUE
TWO_THOUSAND_THIRTEEN
QUOTH_THE_RAVEN,_NEVERMORE.
TO_BE_OR_NOT_TO_BE?
THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG
ADAPTED_FROM_ACM_GREATER_NY_REGION