Istnieje $10^{16}$ miast, ponumerowanych $1, 2, \dots, 10^{16}$.
Dla różnych miast $i, j$ istnieje dwukierunkowa droga między miastem $i$ a miastem $j$ wtedy i tylko wtedy, gdy $\text{lcm}(i, j) = A \cdot \text{gcd}(i, j) + B$.
Odpowiedz na $Q$ zapytań.
W $i$-tym zapytaniu podana jest liczba całkowita $x_i$. Wypisz bitową sumę XOR etykiet wszystkich miast, które są osiągalne z miasta $x_i$ poprzez przebycie zera lub większej liczby dróg.
Wejście
Pierwsza linia zawiera liczby całkowite $A, B$ w tej kolejności, oddzielone spacjami ($1 \le A, B \le 10^8$).
Druga linia zawiera liczbę całkowitą $Q$ ($1 \le Q \le 10^5$).
Każda z kolejnych $Q$ linii zawiera liczbę całkowitą $x_i$ dla $i$-tego zapytania ($1 \le x_i \le 10^{16}$).
Wyjście
Wypisz $Q$ linii.
W $i$-tej linii ($1 \le i \le Q$) wypisz odpowiedź na $i$-te zapytanie.
Przykład
Wejście 1
3 28 4 20 26 7 28
Wyjście 1
28 26 54 108
Wejście 2
81781525 3945925 10 53907475 6160906250298067 3007621769603801 134161450 23675550 4034161385146811 2151358558435 12908151350610 112647860153451 9491287293575
Wyjście 2
53908389 6160906250298067 3007621769603801 9491260218029 2151369618045 4034161385146811 2151369618045 332851610359999 112647860153451 9491260218029
Uwagi
Dla pierwszego przykładu istnienie drogi między miastami $i, j$ jest równoważne $\text{lcm}(i, j) = 3 \cdot \text{gcd}(i, j) + 28$.
- Dla pierwszego zapytania miasta osiągalne z miasta $20$ to $8, 20$.
- Dla drugiego zapytania jedynym miastem osiągalnym z miasta $26$ jest $26$.
- Dla trzeciego zapytania miasta osiągalne z miasta $7$ to $7, 49$.
- Dla czwartego zapytania miasta osiągalne z miasta $28$ to $28, 112$.
Bitowa suma XOR $x \oplus y$ nieujemnych liczb całkowitych $x, y$ jest zdefiniowana następująco:
- W reprezentacji binarnej $x \oplus y$, cyfra na pozycji $2^k$ ($k \ge 0$) wynosi $1$ wtedy i tylko wtedy, gdy dokładnie jedna z cyfr na pozycji $2^k$ w reprezentacjach binarnych $x$ oraz $y$ wynosi $1$; w przeciwnym razie wynosi $0$.
Na przykład $3 \oplus 5 = 6$ (binarnie $011 \oplus 101 = 110$).