Decode Lantern Sequence

In this problem, you are given an encoded lantern sequence which represents a hidden message. The encoding is based on a set of patterns. Each pattern consists of a unique character and its corresponding binary representation. The binary sequence is obtained by concatenating the binary patterns corresponding to characters in the message. Your task is to decode the lantern sequence and retrieve the original message.

Formally, you are given an integer $H$ (the number of patterns) and an integer $N$ (the length of the binary sequence). Then, you are provided with $H$ lines, each containing a single character and its corresponding binary pattern. Finally, you are given the binary sequence of length $N$. It is guaranteed that all binary patterns have the same length, say $L$. The sequence is formed by concatenating the binary codes without any delimiters. You should split the sequence into $\frac{N}{L}$ segments of length $L$ each, and replace each segment with the corresponding character.

For example, if $H = 3$, the mapping is: [ A \to 110, ; B \to 011, ; C \to 101 ] and the binary sequence is "110011101", then splitting into segments: "110", "011", "101" yields the decoded message "ABC".

Your solution must read from standard input and write the result to standard output.

inputFormat

The first line contains two integers $H$ and $N$, where $H$ is the number of patterns and $N$ is the length of the binary sequence. The next $H$ lines each contain a character and its corresponding binary pattern (separated by space). The final line contains a binary string of length $N$ representing the encoded lantern sequence.

outputFormat

Output a single line containing the decoded message.## sample

3 9
A 110
B 011
C 101
110011101

ABC