Viking Hackers

Interview

Time limit1sMemory limit1024 MB

Summary

Split a binary string into 4-bit chunks, map each chunk to its character using a lookup table, and print ? for chunks with no match.

Level: Easy2 of 10
Topics: Hash map, String
Solved: No attempts yet

Problem

Most people know that the Vikings were skilled warriors, but fewer know that they were also good programmers. Carving a runestone meant hours of programming with little room for error. Unfortunately, this made runestones easy targets for Viking hackers, who roamed freely.

You have been assigned to translate a runestone from this era using a reference table of characters and their binary representations. The Vikings had no high-level languages and wrote code directly in 0s and 1s. Since most runestones were eventually hacked, some parts of the code may be wrong.

Input

The first line contains the number of characters $T$ ( $1 \le T \le 16$ ). The next $T$ lines each contain a character (lowercase and uppercase letters a-z and digits may appear) followed by its binary representation, which is always 4 digits long. The last line is a string of $N$ zeros and ones, the runestone to translate. $N$ ( $1 \leq N \leq 4\,000$ ) is divisible by 4. No two different characters in the input have the same binary representation.

Output

Print one line with $N$ characters, the translation of the runestone. Print ? for every part that cannot be translated correctly.

Hint

We learn that 0100 translates to a and 1000 translates to b. The string to translate, 0100100000101000, splits into 0100, 1000, 0010, and 1000. The third chunk is the only one that cannot be translated, so the output is ab?b.

Examples2

Example 1
Input
```
2
a 0100
b 1000
0100100000101000
```
Expected output
```
ab?b
```

Example 2

Input

6
2 0101
P 1101
1 1010
4 1011
O 1110
0 0010
110111110101010010101011

Expected output

P?2?14