High School Programming League Problems Archive

Little John has become obsessed with car plates. He spends entire hours just watching the cars pass by and writing down the plates in his notebook.

After many days trying to find a common pattern for the plates, Little John can't believe what his eyes see. It seems that the plates are generated in such a way that:

1. If divided by its half, the plate appears to be 'mirrored'.
2. Assuming (1) there is exactly one way to make a one-to-one matching between letters and digits.

For example, let us look at one of the plates Little John wrote down:

HAA001

If we make the following matching:

'H'->'1'
'A'->'0'

And then divide the plate by its half:

HAA|001
012 345

Then the plate, according to the matching, appears to be 'mirrored':

P[0] = 'H' P[5] = '1'
P[1] = 'A' P[4] = '0'
P[2] = 'A' P[3] = '0'

Plates consist of L*2 characters, with the first L being capital letters of the english alphabet and the last L being decimal digits.

You are to write a program that finds the i-th plate in the zero-based lexicographically sorted sequence of plates which can be made using the first S letters of the english alphabet plus the decimal digits and having length equal to L*2.

Input

Input starts with three space separated integers: the size of the alphabet (1<=S<=26), half the length of the plates (1<=L<=100) and the number of queries (1<=Q<=300).

Q lines follow, each one having a single integer (0<=I<=10^115), the position of the desired plate in the described sequence.

Output

Output the Q desired plates, each one on a single line.

Example

Input:
10 3 2
0
379960

Output:
AAA000
HAA001

Scoring

For solving this problem you will score 10 points.