Є $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$.
Побітове виключне АБО $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$).