Það eru $10^{16}$ borgir, númeraðar $1, 2, \dots, 10^{16}$.
Fyrir ólíkar borgir $i, j$ liggur tvístefnuvegur á milli borgar $i$ og borgar $j$ ef og aðeins ef $\operatorname{lcm}(i, j) = A \cdot \gcd(i, j) + B$.
Svaraðu $Q$ fyrirspurnum.
Í $i$-tu fyrirspurninni er gefin heiltala $x_i$. Skrifaðu út bitavísað XOR af númerum allra borga sem hægt er að komast til frá borg $x_i$ með því að fara um núll eða fleiri vegi.
Inntak
Fyrsta línan inniheldur heiltölurnar $A, B$ í þessari röð, aðskildar með bilum. ($1 \le A, B \le 10^8$)
Önnur línan inniheldur heiltölu $Q$. ($1 \le Q \le 10^5$)
Hver af næstu $Q$ línum inniheldur heiltölu $x_i$ fyrir $i$-tu fyrirspurnina. ($1 \le x_i \le 10^{16}$)
Úttak
Prentaðu $Q$ línur.
Á $i$-tu línu ($1 \le i \le Q$) skal skrifa út svarið við $i$-tu fyrirspurninni.
Dæmi
Dæmi um inntak 1
3 28 4 20 26 7 28
Dæmi um úttak 1
28 26 54 108
Dæmi um inntak 2
81781525 3945925 10 53907475 6160906250298067 3007621769603801 134161450 23675550 4034161385146811 2151358558435 12908151350610 112647860153451 9491287293575
Dæmi um úttak 2
53908389 6160906250298067 3007621769603801 9491260218029 2151369618045 4034161385146811 2151369618045 332851610359999 112647860153451 9491260218029
Athugasemd
Í fyrra dæminu jafngildir tilvist vegar á milli borga $i, j$ skilyrðinu $\operatorname{lcm}(i, j) = 3 \cdot \gcd(i, j) + 28$.
- Í fyrstu fyrirspurninni eru borgirnar sem komast má til frá borg $20$ borgirnar $8, 20$.
- Í annarri fyrirspurninni er eina borgin sem komast má til frá borg $26$ borgin $26$.
- Í þriðju fyrirspurninni eru borgirnar sem komast má til frá borg $7$ borgirnar $7, 49$.
- Í fjórðu fyrirspurninni eru borgirnar sem komast má til frá borg $28$ borgirnar $28, 112$.
Bitavísað XOR $x \oplus y$ afóneikvæðum heiltölum $x, y$ er skilgreint sem hér segir.
- Í tvíundarframsetningu $x \oplus y$ er tölustafurinn í sæti $2^k$ ($k \ge 0$) jafn $1$ ef og aðeins ef nákvæmlega annar tölustafanna í sæti $2^k$ í tvíundarframsetningum $x$ og $y$ er $1$; annars er hann $0$.
Til dæmis er $3 \oplus 5 = 6$ (í tvíundarkerfi, $011 \oplus 101 = 110$).