Il y a $10^{16}$ villes, numérotées $1, 2, \dots, 10^{16}$.

Pour des villes distinctes $i, j$, il existe une route bidirectionnelle entre la ville $i$ et la ville $j$ si et seulement si $\text{lcm}(i, j) = A \cdot \text{gcd}(i, j) + B$.

Répondez à $Q$ requêtes.

Dans la $i$-ème requête, un entier $x_i$ est donné. Affichez le OU exclusif (XOR) bit à bit des numéros de toutes les villes qui sont accessibles depuis la ville $x_i$ en traversant zéro ou plusieurs routes.

Entrée

La première ligne contient les entiers $A, B$ dans cet ordre, séparés par des espaces. ($1 \le A, B \le 10^8$)

La deuxième ligne contient un entier $Q$. ($1 \le Q \le 10^5$)

Chacune des $Q$ lignes suivantes contient un entier $x_i$ pour la $i$-ème requête. ($1 \le x_i \le 10^{16}$)

Sortie

Affichez $Q$ lignes.

Sur la $i$-ème ligne ($1 \le i \le Q$), affichez la réponse à la $i$-ème requête.

Exemples

Entrée 1

3 28
4
20
26
7
28

Sortie 1

28
26
54
108

Entrée 2

81781525 3945925
10
53907475
6160906250298067
3007621769603801
134161450
23675550
4034161385146811
2151358558435
12908151350610
112647860153451
9491287293575

Sortie 2

53908389
6160906250298067
3007621769603801
9491260218029
2151369618045
4034161385146811
2151369618045
332851610359999
112647860153451
9491260218029

Remarque

Pour le premier exemple, l'existence d'une route entre les villes $i, j$ est équivalente à $\text{lcm}(i, j) = 3 \cdot \text{gcd}(i, j) + 28$.

• Pour la première requête, les villes accessibles depuis la ville $20$ sont $8, 20$.
• Pour la deuxième requête, la seule ville accessible depuis la ville $26$ est $26$.
• Pour la troisième requête, les villes accessibles depuis la ville $7$ sont $7, 49$.
• Pour la quatrième requête, les villes accessibles depuis la ville $28$ sont $28, 112$.

Le OU exclusif (XOR) bit à bit $x \oplus y$ d'entiers positifs ou nuls $x, y$ est défini comme suit.

• Dans la représentation binaire de $x \oplus y$, le chiffre à la position $2^k$ ($k \ge 0$) est $1$ si et seulement si exactement un des chiffres à la position $2^k$ dans les représentations binaires de $x$ et $y$ est $1$ ; sinon, il est $0$.

Par exemple, $3 \oplus 5 = 6$ (en binaire, $011 \oplus 101 = 110$).