Towers of Coins

Interview

Time limit1sMemory limit128 MB

Summary

Given move options 1, K, or L coins in a Nim-like turn game, determine for each pile size whether the first player wins under optimal play.

Level: Easy3 of 10
Topics: Dynamic programming, Game theory
Solved: No attempts yet

Problem

Asen and Boyan play the following game. They fix two distinct positive integers K and L and start with a single tower of N coins. Asen always moves first, then Boyan, then Asen again, then Boyan, and so on, alternating turns. On a turn, the player may remove 1, K, or L coins from the tower. The player who takes the last coin (or coins) wins.

After playing for a long time, Asen realized that in some cases he can always win no matter how Boyan plays, while in all other cases Boyan, playing carefully, can always win no matter how Asen plays. Before the game starts, Asen wants to know which case he is in. Write a program that predicts the result of the game for the given K, L, and N.

Input

The input describes m games.

The first line contains the integers K, L, and m with 1 < K < L < 10 and 3 < m < 50. The second line contains m integers N1, N2, …, Nm, where Ni is the number of coins in the i-th tower (1 ≤ Ni ≤ 1 000 000, i = 1, 2, …, m).

Output

Print a single string of length m consisting of the letters A and B. If Asen wins the i-th game (no matter how the opponent plays), the i-th character must be A. If Boyan wins the i-th game (no matter how Asen plays), the i-th character must be B.

Examples5

Example 1
Input
```
2 3 5
3 12 113 25714 88888
```
Expected output
```
ABAAB
```
Example 2
Input
```
2 3 8
1 2 3 4 5 6 7 8
```
Expected output
```
AAABAAAB
```
Example 3
Input
```
2 4 10
1 2 3 4 5 6 7 8 9 10
```
Expected output
```
AABAABAABA
```
Example 4
Input
```
3 5 10
1 2 3 4 5 6 7 8 9 10
```
Expected output
```
ABABABABAB
```
Example 5
Input
```
3 7 6
6 7 8 9 10 1000000
```
Expected output
```
BABABB
```