TopCoder

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (7/7)

Tags

Description

今天,小 Y 與小 P 來到了 APCS 國。一進入這個國家後,他們在路上,看到了一份寫著密文的文件,以及一本字典。

在 APCS 國裡面,通用的語言是 APCS 語。這個語言是由是由小寫字母去除 aeiou 構成。小 Y 與小 P 撿到的字典中,是一個 APCS 語對應到英文的字典,每個 APCS 語至多只會有一個英文的對應。

而經過 87 天的努力,小 Y 與小 P 終於發現要怎麼破解這個密文了。他們要依序做以下三件事情:

  1. 把密文中所有的英文字母做出 $K$ 的偏移。比如說,當偏移量 $K = 3$ 的時候,字母 a 會被替換成字母 d,字母 b 會被替換成字母 ex 會被替換成字母 a,以此類推。
  2. 把經過上一點處理過後的字串裡面的 aeiou 這五個字母通通換成空格。題目保證經過上一步處理的字串中,不會有兩個連續的 aeiou,並且第一個、最後一個字母也不會是 aeiou
  3. 經過上一點處理後,被空格隔開的文字就是 APCS 語。小 Y 與小 P 需要藉由查字典,來把 APCS 語還原成英文。題目保證每個 APCS 語都有出現在字典中。

而經過以上三部處理後的句子,就是 APCS 語翻譯到英文的結果。

當小 Y 與小 P 通靈出這個解密技巧後,他們覺得解密的過程太累了,於是他們想要請你寫一個程式,來幫助他們解密。

Input Format

輸入的第一行包含兩個正整數 $N, K(1 \leq N \leq 1000, 0 \leq K \leq 25)$,代表 APCS 語到英文的字典的大小(字典裡面的字數),以及進行第一步解密的偏移量。

接下來的 $N$ 行,第 $i$ 行包含兩個以空白隔開的英文小寫字串 $s_i, t_i$,代表 APCS 語中的 $s_i$ 這個字轉換後會變成 $t_i$。題目保證 $s_i, t_i$ 只包含小寫英文字母,並且 $s_i, t_i$ 的長度會介於 $[1, 10]$ 之間。此外,所有的 $s_i$ 皆不會重複。

接下來的一行,包含一個字串 $c$,代表小 Y 與小 P 撿到的密文。這個字串也只包含小寫英文字母,並且長度介於 $[1, 10000]$ 之間。

Output Format

請輸出一個字串於一行,代表解密過後的英文。

Sample Input 1

3 0
xx abc
yyy d
z zzz
xx

Sample Output 1

abc

Sample Input 2

3 1
pq pq
qr qr
rs rs
qr

Sample Output 2

rs

Sample Input 3

8 2
b bad
d dog
c cat
e eat
f frog
ec ecosystem
fd friedfrog
ge game
bcdbcd

Sample Output 3

dog friedfrog frog

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 3~13 $K = 0$,經過第一步轉換後的字串不包含 aeiou 20
3 3~24 經過第一步轉換後的字串不包含 aeiou 30
4 0~34 無額外限制 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 4
1 1000 524288 65536 1 4
2 1000 524288 65536 1 4
3 1000 524288 65536 2 3 4
4 1000 524288 65536 2 3 4
5 1000 524288 65536 2 3 4
6 1000 524288 65536 2 3 4
7 1000 524288 65536 2 3 4
8 1000 524288 65536 2 3 4
9 1000 524288 65536 2 3 4
10 1000 524288 65536 2 3 4
11 1000 524288 65536 2 3 4
12 1000 524288 65536 2 3 4
13 1000 524288 65536 2 3 4
14 1000 524288 65536 3 4
15 1000 524288 65536 3 4
16 1000 524288 65536 3 4
17 1000 524288 65536 3 4
18 1000 524288 65536 3 4
19 1000 524288 65536 3 4
20 1000 524288 65536 3 4
21 1000 524288 65536 3 4
22 1000 524288 65536 3 4
23 1000 524288 65536 3 4
24 1000 524288 65536 3 4
25 1000 524288 65536 4
26 1000 524288 65536 4
27 1000 524288 65536 4
28 1000 524288 65536 4
29 1000 524288 65536 4
30 1000 524288 65536 4
31 1000 524288 65536 4
32 1000 524288 65536 4
33 1000 524288 65536 4
34 1000 524288 65536 4