On $10^{16}$ kaupunkia, jotka on numeroitu $1, 2, \dots, 10^{16}$.
Eri kaupunkien $i, j$ osalta kaupungin $i$ ja kaupungin $j$ välillä on kaksisuuntainen tie täsmälleen silloin, kun $\operatorname{lcm}(i, j) = A \cdot \gcd(i, j) + B$.
Vastaa $Q$ kyselyyn.
Kyselyssä $i$ annetaan kokonaisluku $x_i$. Tulosta kaikkien niiden kaupunkien numeroiden bittikohtainen XOR, joihin pääsee kaupungista $x_i$ kulkemalla nolla tai useampia teitä.
Syöte
Ensimmäinen rivi sisältää kokonaisluvut $A, B$ tässä järjestyksessä välilyönnein erotettuina. ($1 \le A, B \le 10^8$)
Toinen rivi sisältää kokonaisluvun $Q$. ($1 \le Q \le 10^5$)
Kukin seuraavista $Q$ rivistä sisältää kokonaisluvun $x_i$ kyselyä $i$ varten. ($1 \le x_i \le 10^{16}$)
Tuloste
Tulosta $Q$ riviä.
Tulosta riville $i$ ($1 \le i \le Q$) vastaus kyselyyn $i$.
Esimerkit
Esimerkkisyöte 1
3 28 4 20 26 7 28
Esimerkkituloste 1
28 26 54 108
Esimerkkisyöte 2
81781525 3945925 10 53907475 6160906250298067 3007621769603801 134161450 23675550 4034161385146811 2151358558435 12908151350610 112647860153451 9491287293575
Esimerkkituloste 2
53908389 6160906250298067 3007621769603801 9491260218029 2151369618045 4034161385146811 2151369618045 332851610359999 112647860153451 9491260218029
Huomautus
Ensimmäisessä esimerkissä tien olemassaolo kaupunkien $i, j$ välillä vastaa ehtoa $\operatorname{lcm}(i, j) = 3 \cdot \gcd(i, j) + 28$.
- Ensimmäisessä kyselyssä kaupungista $20$ saavutettavat kaupungit ovat $8, 20$.
- Toisessa kyselyssä ainoa kaupungista $26$ saavutettava kaupunki on $26$.
- Kolmannessa kyselyssä kaupungista $7$ saavutettavat kaupungit ovat $7, 49$.
- Neljännessä kyselyssä kaupungista $28$ saavutettavat kaupungit ovat $28, 112$.
Ei-negatiivisten kokonaislukujen $x, y$ bittikohtainen XOR $x \oplus y$ määritellään seuraavasti.
- Luvun $x \oplus y$ binääriesityksessä kohdan $2^k$ ($k \ge 0$) bitti on $1$ täsmälleen silloin, kun tasan toinen lukujen $x$ ja $y$ binääriesitysten kohdan $2^k$ biteistä on $1$; muuten se on $0$.
Esimerkiksi $3 \oplus 5 = 6$ (binäärinä $011 \oplus 101 = 110$).