Det finns $10^{16}$ städer, numrerade $1, 2, \dots, 10^{16}$.
För skilda städer $i, j$ finns det en dubbelriktad väg mellan stad $i$ och stad $j$ om och endast om $\operatorname{lcm}(i, j) = A \cdot \gcd(i, j) + B$.
Besvara $Q$ frågor.
I den $i$-te frågan ges ett heltal $x_i$. Skriv ut det bitvisa XOR-värdet av numren på alla städer som kan nås från stad $x_i$ genom att färdas längs noll eller flera vägar.
Indata
Den första raden innehåller heltalen $A, B$ i denna ordning, åtskilda av blanksteg. ($1 \le A, B \le 10^8$)
Den andra raden innehåller ett heltal $Q$. ($1 \le Q \le 10^5$)
Var och en av de följande $Q$ raderna innehåller ett heltal $x_i$ för den $i$-te frågan. ($1 \le x_i \le 10^{16}$)
Utdata
Skriv ut $Q$ rader.
På den $i$-te raden ($1 \le i \le Q$) ska du skriva ut svaret på den $i$-te frågan.
Exempel
Exempelindata 1
3 28 4 20 26 7 28
Exempelutdata 1
28 26 54 108
Exempelindata 2
81781525 3945925 10 53907475 6160906250298067 3007621769603801 134161450 23675550 4034161385146811 2151358558435 12908151350610 112647860153451 9491287293575
Exempelutdata 2
53908389 6160906250298067 3007621769603801 9491260218029 2151369618045 4034161385146811 2151369618045 332851610359999 112647860153451 9491260218029
Förklaring
För det första exemplet är existensen av en väg mellan städerna $i, j$ ekvivalent med $\operatorname{lcm}(i, j) = 3 \cdot \gcd(i, j) + 28$.
- För den första frågan är städerna som kan nås från stad $20$ lika med $8, 20$.
- För den andra frågan är den enda staden som kan nås från stad $26$ lika med $26$.
- För den tredje frågan är städerna som kan nås från stad $7$ lika med $7, 49$.
- För den fjärde frågan är städerna som kan nås från stad $28$ lika med $28, 112$.
Det bitvisa XOR-värdet $x \oplus y$ för icke-negativa heltal $x, y$ definieras enligt följande.
- I den binära representationen av $x \oplus y$ är siffran på platsen $2^k$ ($k \ge 0$) lika med $1$ om och endast om exakt en av siffrorna på platsen $2^k$ i de binära representationerna av $x$ och $y$ är $1$; annars är den $0$.
Till exempel är $3 \oplus 5 = 6$ (binärt $011 \oplus 101 = 110$).