ישנן $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$).