Det finnes $10^{16}$ byer, nummerert $1, 2, \dots, 10^{16}$.
For ulike byer $i, j$ går det en toveis vei mellom by $i$ og by $j$ hvis og bare hvis $\operatorname{lcm}(i, j) = A \cdot \gcd(i, j) + B$.
Svar på $Q$ spørringer.
I den $i$-te spørringen gis et heltall $x_i$. Skriv ut den bitvise XOR-verdien av numrene til alle byer som kan nås fra by $x_i$ ved å følge null eller flere veier.
Inndata
Den første linjen inneholder heltallene $A, B$ i denne rekkefølgen, adskilt med mellomrom. ($1 \le A, B \le 10^8$)
Den andre linjen inneholder et heltall $Q$. ($1 \le Q \le 10^5$)
Hver av de påfølgende $Q$ linjene inneholder et heltall $x_i$ for den $i$-te spørringen. ($1 \le x_i \le 10^{16}$)
Utdata
Skriv ut $Q$ linjer.
På den $i$-te linjen ($1 \le i \le Q$) skal du skrive ut svaret på den $i$-te spørringen.
Eksempler
Eksempelinndata 1
3 28 4 20 26 7 28
Eksempelutdata 1
28 26 54 108
Eksempelinndata 2
81781525 3945925 10 53907475 6160906250298067 3007621769603801 134161450 23675550 4034161385146811 2151358558435 12908151350610 112647860153451 9491287293575
Eksempelutdata 2
53908389 6160906250298067 3007621769603801 9491260218029 2151369618045 4034161385146811 2151369618045 332851610359999 112647860153451 9491260218029
Forklaring
For det første eksempelet tilsvarer eksistensen av en vei mellom byene $i, j$ at $\operatorname{lcm}(i, j) = 3 \cdot \gcd(i, j) + 28$.
- For den første spørringen er byene som kan nås fra by $20$ lik $8, 20$.
- For den andre spørringen er den eneste byen som kan nås fra by $26$ lik $26$.
- For den tredje spørringen er byene som kan nås fra by $7$ lik $7, 49$.
- For den fjerde spørringen er byene som kan nås fra by $28$ lik $28, 112$.
Den bitvise XOR-verdien $x \oplus y$ for ikke-negative heltall $x, y$ er definert som følger.
- I den binære representasjonen av $x \oplus y$ er sifferet på $2^k$-plassen ($k \ge 0$) lik $1$ hvis og bare hvis nøyaktig ett av sifrene på $2^k$-plassen i de binære representasjonene av $x$ og $y$ er $1$; ellers er det $0$.
For eksempel er $3 \oplus 5 = 6$ (i binær form, $011 \oplus 101 = 110$).