YOU: "It seems that no-one really saw you around very much. Why is that?"

LESLIE: "Well, my role was proofreading the speeches before the ball. Figured I didn't really need to be at the hall for that, with all the noise and chaos going on. So I did most of the actual work at home, then came in at around five."

YOU: "What was in the speeches? Now that the event is off, can you tell me?"

LESLIE: "Yeah, of course. Let's see... There was one from Ray, about his latest developments on his new problem-setting platform. Tom had a big one planned too, about how proud she was of everyone's progress this year. And then there was Kevin's."

YOU: "What was he going to talk about?"

LESLIE: "Honestly, I don't know. All he'd written down was 'key statistic: tasks completed 90% faster, and you can't even tell the difference.' There was also an advertisement for the next AUCPL round. It was really nice actually. I think he was just going to wing the rest of it. I sort of wish he'd written more down. I guess we'll never know what he had planned."

Leslie is the chief editor of the event's speeches. She is currently proofreading Ray's speech, which is a string of length ~n~ consisting only of lowercase English letters from a to j.

Leslie has very strong opinions about word choice. For each character ~c~, she has decided that every occurrence of ~c~ should be replaced by a specific string ~S_c~. These replacement strings may have different lengths.

Applying Leslie's editing process once means simultaneously replacing every character in the current speech with its corresponding string. This produces a new, longer speech.

Unfortunately, Leslie is a little overzealous. After applying the process once, she forgets she has already done so and applies it again, and again. She only notices and stops her process once she has applied the process exactly ~k~ times. If ~k = 0~, she does not apply the process at all.

After Leslie stops, the speech may be extremely large. Given ~q~ queries, Leslie now wants to know which character appears at each specified position in the final speech.

Input

The first line contains two integers, ~n~ and ~k~ ~(1 \le n \le 10, 0 \le k \le 10^{18})~, representing the length of Ray's original speech and the number of times Leslie applies her editing process.

The second line contains Ray's speech, a string of length ~n~ consisting only of lowercase English letters from a to j.

The next ~10~ lines contain the replacement strings for a, b, ..., j in order. Each replacement string contains only characters from a to j, and has length between ~2~ and ~10~, inclusive.

The next line contains a single integer ~q~ ~(1 \le q \le 10^5)~, the number of queries.

The next ~q~ lines each contain a single integer ~i~ ~(1 \leq i \leq 10^{18})~, representing a 1-indexed position in the final speech. It is guaranteed that ~i~ does not exceed the length of the speech after the editing process finishes.

Output

For each query, output the character at position ~i~ of the final speech on its own line.

Example

Input 1

2 2
ba
ab
cab
cc
aaa
aaa
aaa
aaa
aaa
aaa
aaa
5
6
7
12
1
5

Output 1

a
b
b
c
c

Input 2

2 3
hi
bid
cafe
dead
each
fed
gag
heed
idea
jab
ace
8
2
3
5
7
11
13
17
19

Output 2

c
e
i
c
f
d
d
a

Input 3

1 59
b
aa
ab
jj
jj
jj
jj
jj
jj
jj
jj
4
1
2
576460752303423487
576460752303423488

Output 3

a
a
a
b