To celebrate the ~20^\text{th}~ anniversary of Home Alone 4, Wesley Alexander Ting-Zhang Leung decided to re-watch it (a ~613^\text{th}~ time).

While watching the movie, Wesley reminisced,

I hate this problem.

With the flavour text out of the way, Wesley noted that his Huffman Encoding was wrong; however, Wesley realized that he could still recover the Wesley-ically smallest message.

If two messages have different lengths, the shorter one is Wesley-ically shorter.

If two messages have the same length, the first character that differs between a Wesley-ically smaller string and a larger one will appear earlier in the alphabet for the Wesley-ically smaller string.

Wesley has ~N~ pairings of a lowercase letter to a binary string, and the encoded message, ~M~, is made up of the binary strings of characters using the pairings.

Can you help Wesley recover the Wesley-ically smallest message?

Constraints

~1 \le N \le 100~

~1 \le |M| \le 10^4~

Note that ~|M|~ denotes the length of the string ~M~.

~M~ and each binary string will only contain ~0~ or ~1~.

The length of each binary string is at most ~10~ characters.

The binary strings mapped from the same lowercase letter are all the same length.

Note that a letter can map to multiple binary strings.

The data guarantee that there is at least one valid, decoded message.

Subtask 1 [20%]

~N = 1~

The one pairing will have a binary string length of ~1~.

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line will contain ~N~ and ~|M|~, the number of pairings of a lowercase letter to a binary string and the length of the encoded string, respectively.

The second line will contain ~M~, the encoded message.

The next ~N~ lines will contain a lowercase letter and a binary string, a pairing from that lowercase letter to that binary string.

Output Specification

Output the Wesley-ically smallest message that could be encoded to create ~S~.

Sample Input 1

3 5
10101
a 10
b 1
c 0

Sample Output 1

aab

Sample Input 2

5 20
10001010001000110001
h 0
h 1
r 0100
i 10001
f 10001

Sample Output 2

frhff