Ci sono $10^{16}$ città, numerate $1, 2, \dots, 10^{16}$.
Per città distinte $i, j$, esiste una strada bidirezionale tra la città $i$ e la città $j$ se e solo se $\operatorname{lcm}(i, j) = A \cdot \gcd(i, j) + B$.
Rispondi a $Q$ query.
Nella $i$-esima query viene fornito un intero $x_i$. Stampa lo XOR bit a bit delle etichette di tutte le città raggiungibili dalla città $x_i$ percorrendo zero o più strade.
Input
La prima riga contiene gli interi $A, B$ in quest'ordine, separati da spazi. ($1 \le A, B \le 10^8$)
La seconda riga contiene un intero $Q$. ($1 \le Q \le 10^5$)
Ciascuna delle successive $Q$ righe contiene un intero $x_i$ per la $i$-esima query. ($1 \le x_i \le 10^{16}$)
Output
Stampa $Q$ righe.
Sulla $i$-esima riga ($1 \le i \le Q$), stampa la risposta alla $i$-esima query.
Esempi
Input di esempio 1
3 28 4 20 26 7 28
Output di esempio 1
28 26 54 108
Input di esempio 2
81781525 3945925 10 53907475 6160906250298067 3007621769603801 134161450 23675550 4034161385146811 2151358558435 12908151350610 112647860153451 9491287293575
Output di esempio 2
53908389 6160906250298067 3007621769603801 9491260218029 2151369618045 4034161385146811 2151369618045 332851610359999 112647860153451 9491260218029
Note
Per il primo esempio, l'esistenza di una strada tra le città $i, j$ è equivalente a $\operatorname{lcm}(i, j) = 3 \cdot \gcd(i, j) + 28$.
- Per la prima query, le città raggiungibili dalla città $20$ sono $8, 20$.
- Per la seconda query, l'unica città raggiungibile dalla città $26$ è $26$.
- Per la terza query, le città raggiungibili dalla città $7$ sono $7, 49$.
- Per la quarta query, le città raggiungibili dalla città $28$ sono $28, 112$.
Lo XOR bit a bit $x \oplus y$ di interi non negativi $x, y$ è definito come segue.
- Nella rappresentazione binaria di $x \oplus y$, la cifra nella posizione $2^k$ ($k \ge 0$) è $1$ se e solo se esattamente una delle cifre nella posizione $2^k$ nelle rappresentazioni binarie di $x$ e $y$ è $1$; altrimenti è $0$.
Ad esempio, $3 \oplus 5 = 6$ (in binario, $011 \oplus 101 = 110$).