Es gibt $10^{16}$ Städte, die mit $1, 2, \dots, 10^{16}$ nummeriert sind.
Für verschiedene Städte $i, j$ gibt es genau dann eine Straße in beide Richtungen zwischen Stadt $i$ und Stadt $j$, wenn $\operatorname{lcm}(i, j) = A \cdot \gcd(i, j) + B$ gilt.
Beantworte $Q$ Anfragen.
In der $i$-ten Anfrage ist eine ganze Zahl $x_i$ gegeben. Gib das bitweise XOR der Nummern aller Städte aus, die von Stadt $x_i$ aus über null oder mehr Straßen erreichbar sind.
Eingabe
Die erste Zeile enthält die ganzen Zahlen $A, B$ in dieser Reihenfolge, getrennt durch Leerzeichen. ($1 \le A, B \le 10^8$)
Die zweite Zeile enthält eine ganze Zahl $Q$. ($1 \le Q \le 10^5$)
Jede der folgenden $Q$ Zeilen enthält eine ganze Zahl $x_i$ für die $i$-te Anfrage. ($1 \le x_i \le 10^{16}$)
Ausgabe
Gib $Q$ Zeilen aus.
Gib in der $i$-ten Zeile ($1 \le i \le Q$) die Antwort auf die $i$-te Anfrage aus.
Beispiele
Beispieleingabe 1
3 28 4 20 26 7 28
Beispielausgabe 1
28 26 54 108
Beispieleingabe 2
81781525 3945925 10 53907475 6160906250298067 3007621769603801 134161450 23675550 4034161385146811 2151358558435 12908151350610 112647860153451 9491287293575
Beispielausgabe 2
53908389 6160906250298067 3007621769603801 9491260218029 2151369618045 4034161385146811 2151369618045 332851610359999 112647860153451 9491260218029
Hinweis
Für das erste Beispiel ist die Existenz einer Straße zwischen den Städten $i, j$ äquivalent zu $\operatorname{lcm}(i, j) = 3 \cdot \gcd(i, j) + 28$.
- Für die erste Anfrage sind die von Stadt $20$ aus erreichbaren Städte $8, 20$.
- Für die zweite Anfrage ist die einzige von Stadt $26$ aus erreichbare Stadt $26$.
- Für die dritte Anfrage sind die von Stadt $7$ aus erreichbaren Städte $7, 49$.
- Für die vierte Anfrage sind die von Stadt $28$ aus erreichbaren Städte $28, 112$.
Das bitweise XOR $x \oplus y$ nichtnegativer ganzer Zahlen $x, y$ ist wie folgt definiert.
- In der Binärdarstellung von $x \oplus y$ ist die Ziffer an der Stelle $2^k$ ($k \ge 0$) genau dann $1$, wenn genau eine der Ziffern an der Stelle $2^k$ in den Binärdarstellungen von $x$ und $y$ gleich $1$ ist; andernfalls ist sie $0$.
Beispielsweise gilt $3 \oplus 5 = 6$ (binär $011 \oplus 101 = 110$).