توجد $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 البتية لأرقام جميع المدن التي يمكن الوصول إليها من المدينة $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$).