Существует $10^{16}$ городов, пронумерованных числами $1, 2, \dots, 10^{16}$.

Для различных городов $i, j$ существует двусторонняя дорога между городом $i$ и городом $j$ тогда и только тогда, когда $\text{lcm}(i, j) = A \cdot \text{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$ эквивалентно $\text{lcm}(i, j) = 3 \cdot \text{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$).