|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
G - Computer DJ
Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)
A very famous DJ has been recently invited to play in the closing party of a Computer Science conference. Trying to impress the participants of the event, he decided to use a program in order to choose the songs he would play at this party. However, the result was a disaster, since the way the program chose the songs was quite weird and repetitive.
First of all, the DJ has selected $N$ songs among the set of songs he had available. The program used by the DJ then labels each of the songs using one different character from $\texttt{‘A’}$ to $\texttt{‘Z’}$. The $i^{\text{th}}$ song is labeled using the $i^{\text{th}}$ character of the sequence $\texttt{‘A’} - \texttt{‘Z’}$. The program chooses the songs to be played in the party in the order that their labels appear in the following infinite sequence of characters: first come all the words with one character in lexicographical order; then all the words with two characters in lexicographical order; then all the words with three characters in lexicographical order; and so on. For $N = 3$, this sequence would be $\texttt{ABCAAABACBABBBCCACBCCAAAAABAACABAABBABC}$...
At the end of the party, some people asked the DJ if he remembered which the first song played was. Others would like to know which the $25^{\text{th}}$ was, and so on. The DJ remembers nothing but the strange pattern of repetition of the songs, so he urges you to help him and write a program which answers such queries.
Input
The input contains several test cases. Each test case consists of three lines. The first line of a test case contains two integers $N$ and $Q$ indicating respectively the number of songs chosen by the DJ and the number of queries made by the participants ($1 \leq N \leq 26$ and $1 \leq Q \leq 1000$). In the second line, there will be the N titles of the songs (the title of a song is a chain of alphanumerical characters of at least one and at most $100$ characters) separated by single spaces. The last line of a test case contains a sequence of queries. Each query is a number $k$ $(1 \leq k \leq 100000000)$ corresponding to the $k$-th song played in the party. The end of the input is indicated by $N = Q = 0$.
The input must be read from standard input.
Output
For each query number k in a test case, you shall print a single line containing the name of the $k^{\text{th}}$ song played in the party. A blank line must follow each test case.
The output must be written to standard output.
Sample test(s)
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
Output
S2
S5
S9
Pathethique
TurkishMarch
Winter
Pathethique
Winter