มีเมืองอยู่ $10^{16}$ แห่ง ซึ่งมีหมายเลขกำกับคือ $1, 2, \dots, 10^{16}$
สำหรับเมือง $i, j$ ที่แตกต่างกัน จะมีถนนสองทิศทางเชื่อมระหว่างเมือง $i$ และเมือง $j$ ก็ต่อเมื่อ $\operatorname{lcm}(i, j) = A \cdot \gcd(i, j) + B$
จงตอบคำถาม $Q$ ข้อ
ในคำถามข้อที่ $i$ จะกำหนดจำนวนเต็ม $x_i$ มาให้ จงแสดงผลลัพธ์ของการดำเนินการ XOR แบบบิต (bitwise XOR) ของหมายเลขเมืองทั้งหมดที่สามารถเดินทางไปถึงได้จากเมือง $x_i$ โดยผ่านถนนศูนย์สายหรือมากกว่า
ข้อมูลนำเข้า
บรรทัดแรกประกอบด้วยจำนวนเต็ม $A, B$ ตามลำดับ คั่นด้วยช่องว่าง ($1 \le A, B \le 10^8$)
บรรทัดที่สองประกอบด้วยจำนวนเต็ม $Q$ ($1 \le Q \le 10^5$)
แต่ละบรรทัดใน $Q$ บรรทัดถัดไป ประกอบด้วยจำนวนเต็ม $x_i$ สำหรับคำถามข้อที่ $i$ ($1 \le x_i \le 10^{16}$)
ข้อมูลส่งออก
พิมพ์คำตอบ $Q$ บรรทัด
ในบรรทัดที่ $i$ ($1 \le i \le Q$) ให้แสดงคำตอบของคำถามข้อที่ $i$
ตัวอย่าง
ข้อมูลนำเข้าตัวอย่างที่ 1
3 28 4 20 26 7 28
ข้อมูลส่งออกตัวอย่างที่ 1
28 26 54 108
ข้อมูลนำเข้าตัวอย่างที่ 2
81781525 3945925 10 53907475 6160906250298067 3007621769603801 134161450 23675550 4034161385146811 2151358558435 12908151350610 112647860153451 9491287293575
ข้อมูลส่งออกตัวอย่างที่ 2
53908389 6160906250298067 3007621769603801 9491260218029 2151369618045 4034161385146811 2151369618045 332851610359999 112647860153451 9491260218029
หมายเหตุ
สำหรับตัวอย่างแรก การมีถนนเชื่อมระหว่างเมือง $i, j$ สมมูลกับ $\operatorname{lcm}(i, j) = 3 \cdot \gcd(i, j) + 28$
- สำหรับคำถามข้อแรก เมืองที่เดินทางไปถึงได้จากเมือง $20$ คือ $8, 20$
- สำหรับคำถามข้อที่สอง เมืองเดียวที่เดินทางไปถึงได้จากเมือง $26$ คือ $26$
- สำหรับคำถามข้อที่สาม เมืองที่เดินทางไปถึงได้จากเมือง $7$ คือ $7, 49$
- สำหรับคำถามข้อที่สี่ เมืองที่เดินทางไปถึงได้จากเมือง $28$ คือ $28, 112$
การดำเนินการ XOR แบบบิต $x \oplus y$ ของจำนวนเต็มไม่ลบ $x, y$ นิยามดังต่อไปนี้
- ในการเขียนแทนด้วยเลขฐานสองของ $x \oplus y$ เลขโดดในหลัก $2^k$ ($k \ge 0$) จะเป็น $1$ ก็ต่อเมื่อมีเลขโดดในหลัก $2^k$ ของการเขียนแทนด้วยเลขฐานสองของ $x$ และ $y$ เพียงตัวเดียวเท่านั้นที่เป็น $1$ มิฉะนั้นจะเป็น $0$
ตัวอย่างเช่น $3 \oplus 5 = 6$ (ในระบบเลขฐานสองคือ $011 \oplus 101 = 110$)