Computer DJ

Time limit1sMemory limit128 MB

Summary

Given N labeled songs, map the k-th character of the infinite string of all words over A..Z in length-then-lex order back to its song title.

Level: Medium5 of 10
Topics: Math, Combinatorics, Implementation, Brute force
Solved: No attempts yet

Problem

A very famous DJ has recently been invited to play at the closing party of a Computer Science conference. To impress the participants, he decided to use a program to choose the songs he would play. The result, however, was a disaster, because the way the program picked songs was quite strange and repetitive.

First, the DJ selected $N$ songs from those available. The program then labels each song with a distinct character from 'A' to 'Z': the $i$ -th song is labeled with the $i$ -th character of the sequence 'A'-'Z'. The program plays the songs in the order their labels appear in the following infinite string of characters: first come all words of length 1 in lexicographical order, then all words of length 2 in lexicographical order, then all words of length 3, and so on. For $N = 3$ , this string begins ABCAAABACBABBBCCACBCCAAAAABAACABAABBABC...

After the party, some people asked the DJ which song was played first. Others wanted to know which one was the 25th, and so on. The DJ remembers nothing but this strange repetition pattern, so he asks you to write a program that answers such queries.

Input

The input contains several test cases. Each test case consists of three lines. The first line contains two integers $N$ and $Q$ , the number of songs the DJ chose and the number of queries the participants made ( $1 \le N \le 26$ and $1 \le Q \le 1000$ ). The second line contains the $N$ song titles separated by single spaces (each title is a string of alphanumeric characters, at least 1 and at most 100 characters long). The third line contains a sequence of queries. Each query is a number $k$ ( $1 \le k \le 100\,000\,000$ ) referring to the $k$ -th song played at the party. The end of the input is indicated by $N = Q = 0$ .

Output

For each query $k$ in a test case, print a single line with the name of the $k$ -th song played at the party. Print a blank line after each test case.

Examples3

Example 1

Input

10 3
S0 S1 S2 S3 S4 S5 S6 S7 S8 S9
3 6 10
3 5
Pathethique TurkishMarch Winter
1 2 3 4 16
0 0

Expected output

S2
S5
S9

Pathethique
TurkishMarch
Winter
Pathethique
Winter

Example 2

Input

2 7
Do Re
1 2 3 6 7 10 11
0 0

Expected output

Do
Re
Do
Re
Re
Re
Do

Example 3
Input
```
3 3
X Y Z
21 22 100
0 0
```
Expected output
```
Z
X
Z
```