Strange Base-k Representation

Alice is exploring an unusual numeral system. In a conventional base-\( k \) representation of an integer \( n \), we have

[ n = \sum_{i=0}^{m-1} d_i, k^i, \quad 0 \le d_i < k, ]

However, Alice prefers a strange base-\( k \) representation where the only change is that instead of \(0 \le d_i .

The conversion is defined as follows. For a given nonnegative integer \(n\):

• If \(n = 0\), its strange representation is the single digit a[0].
• If \(n > 0\), repeatedly compute the remainder \(r = n \mod k\) and let the corresponding digit be a[r]. Then update \(n = \lfloor n/k \rfloor\). Once \(n\) becomes 0, the representation is the reverse of the sequence of obtained digits.

Your task is to convert \(q\) decimal integers \(n_1, n_2, \dots, n_q\) into their strange base-\( k \) representations.

inputFormat

The input consists of:

• The first line contains two integers \(k\) and \(D\) (with \(D = k\)).
• The second line contains \(D\) integers representing the sequence \(a_0, a_1, \dots, a_{D-1}\).
• The third line contains an integer \(q\), the number of queries.
• Each of the next \(q\) lines contains a nonnegative integer \(n\) in decimal format.

outputFormat

For each query, output a line containing the strange base-\( k \) representation of the given integer. Do not include any extra spaces or characters.

sample

10 10
0 9 8 7 6 5 4 3 2 1
3
0
47
100

0
63
900