Terdapat $10^{16}$ kota yang diberi label $1, 2, \dots, 10^{16}$.
Untuk kota-kota berbeda $i, j$, terdapat jalan dua arah antara kota $i$ dan kota $j$ jika dan hanya jika $\operatorname{lcm}(i, j) = A \cdot \gcd(i, j) + B$.
Jawablah $Q$ kueri.
Pada kueri ke-$i$, diberikan sebuah bilangan bulat $x_i$. Keluarkan hasil XOR bitwise dari label semua kota yang dapat dicapai dari kota $x_i$ dengan melewati nol atau lebih jalan.
Masukan
Baris pertama berisi bilangan bulat $A, B$ dalam urutan tersebut, dipisahkan oleh spasi. ($1 \le A, B \le 10^8$)
Baris kedua berisi sebuah bilangan bulat $Q$. ($1 \le Q \le 10^5$)
Masing-masing dari $Q$ baris berikutnya berisi sebuah bilangan bulat $x_i$ untuk kueri ke-$i$. ($1 \le x_i \le 10^{16}$)
Keluaran
Cetak $Q$ baris.
Pada baris ke-$i$ ($1 \le i \le Q$), keluarkan jawaban untuk kueri ke-$i$.
Contoh
Contoh Masukan 1
3 28 4 20 26 7 28
Contoh Keluaran 1
28 26 54 108
Contoh Masukan 2
81781525 3945925 10 53907475 6160906250298067 3007621769603801 134161450 23675550 4034161385146811 2151358558435 12908151350610 112647860153451 9491287293575
Contoh Keluaran 2
53908389 6160906250298067 3007621769603801 9491260218029 2151369618045 4034161385146811 2151369618045 332851610359999 112647860153451 9491260218029
Catatan
Untuk contoh pertama, keberadaan jalan antara kota $i, j$ setara dengan $\operatorname{lcm}(i, j) = 3 \cdot \gcd(i, j) + 28$.
- Untuk kueri pertama, kota-kota yang dapat dicapai dari kota $20$ adalah $8, 20$.
- Untuk kueri kedua, satu-satunya kota yang dapat dicapai dari kota $26$ adalah $26$.
- Untuk kueri ketiga, kota-kota yang dapat dicapai dari kota $7$ adalah $7, 49$.
- Untuk kueri keempat, kota-kota yang dapat dicapai dari kota $28$ adalah $28, 112$.
XOR bitwise $x \oplus y$ dari bilangan bulattak negatif $x, y$ didefinisikan sebagai berikut.
- Dalam representasi biner dari $x \oplus y$, digit pada nilai tempat $2^k$ ($k \ge 0$) bernilai $1$ jika dan hanya jika tepat satu dari digit pada nilai tempat $2^k$ dalam representasi biner dari $x$ dan $y$ bernilai $1$; selain itu, nilainya adalah $0$.
Sebagai contoh, $3 \oplus 5 = 6$ (dalam biner, $011 \oplus 101 = 110$).