Keylogger

/problems/keylogger/file/statement/en/img-0001.jpg
Photo by Christian Söderberg, no rights reserved.

Thore likes mechanical keyboards. He uses a highly customised design, where every key has been carefully selected for resistance, actuation point, tactile feedback, travel distance, and clickiness. He finds the sound of the mechanical keys very satisfying. Your office is next to Thore’s and you hear the click-clock-clinging of him typing. After a while you notice that every key has a unique sound.

Given the sounds from Thore’s office, can you hear what he’s typing?

Each key except shift can be tapped, and has its own distinctive sound when tapped. The spacebar inserts a single space character at the end. The letter keys insert a single letter in their upper- or lowercase form at the end. For instance, tapping M inserts the lowercase “m” or the uppercase “M”. The delete key removes a single symbol, starting from the latest inserted symbol, provided there are symbols left. (Otherwise, nothing happens.)

Case is determined by the keyboard’s state, which is either capslocked or not, and whether the shift key is held down. Tapping the capslock key switches the state to capslocked or back. In the capslocked state, all letter keys produce their uppercase form. This behaviour is inverted when the shift key is held down. For instance, if the keyboard is not capslocked and shift is held down then tapping M inserts an uppercase “M”. Likewise, if the keyboard is capslocked and shift is held down then tapping M inserts a lowercase “m”.

The shift key is never tapped. Instead, it is either held down or released, each with its own sound. Thore’s keyboard has a single shift key (under his left thumb), so the two sounds must alternate.

Thore starts the work day with the keyboard not in capslocked state and with the shift key not held down.

The following table shows the sound each key makes. You hear no other sounds than those listed in the table.

\includegraphics[width=0.7\textwidth ]{img/table-en.pdf}

Input

The first line of input is an integer $N$, where $N > 0$, the number of sounds you hear from Thore’s office. The following $N$ lines each contain a single sound, matching one of the keys in the table.

Output

Print the resulting text.

Scoring

Group

Points

Limits

1

20

Thore only types letters, $N \leq 1\, 000$

2

30

Thore can also use spacebar, capslock, and delete, $N \leq 100\, 000$

3

50

Thore can use any key, $N \leq 100\, 000$

Sample Input 1 Sample Output 1
26
clank
bong
click
tap
poing
clonk
clack
ping
tip
cloing
tic
cling
bing
pong
clang
pang
clong
tac
boing
boink
cloink
rattle
clock
toc
clink
tuc
abcdefghijklmnopqrstuvwxyz
Sample Input 2 Sample Output 2
14
bump
tip
whack
bump
clock
clank
pong
boink
whack
pang
tip
tuc
tuc
clank
I want pizza
Sample Input 3 Sample Output 3
10
dink
pong
clang
whack
bump
click
thumb
clank
pang
boing
NO cAPS