Có $10^{16}$ thành phố, được đánh số từ $1, 2, \dots, 10^{16}$.

Với hai thành phố phân biệt $i, j$, tồn tại một con đường hai chiều giữa thành phố $i$ và thành phố $j$ khi và chỉ khi $\text{lcm}(i, j) = A \cdot \text{gcd}(i, j) + B$.

Hãy trả lời $Q$ truy vấn. Trong truy vấn thứ $i$, một số nguyên $x_i$ được đưa ra. Hãy tính XOR bit của nhãn của tất cả các thành phố có thể đi đến được từ thành phố $x_i$ bằng cách đi qua không hoặc nhiều con đường.

Dữ liệu vào

• Dòng đầu tiên chứa các số nguyên $A, B$ theo thứ tự, cách nhau bởi dấu cách ($1 \le A, B \le 10^8$).
• Dòng thứ hai chứa số nguyên $Q$ ($1 \le Q \le 10^5$).
• Mỗi dòng trong $Q$ dòng tiếp theo chứa một số nguyên $x_i$ cho truy vấn thứ $i$ ($1 \le x_i \le 10^{16}$).

Dữ liệu ra

• In ra $Q$ dòng.
• Trên dòng thứ $i$ ($1 \le i \le Q$), in ra kết quả cho truy vấn thứ $i$.

Ví dụ

Dữ liệu vào 1

3 28
4
20
26
7
28

Dữ liệu ra 1

28
26
54
108

Ghi chú

Đối với ví dụ đầu tiên, sự tồn tại của một con đường giữa các thành phố $i, j$ tương đương với $\text{lcm}(i, j) = 3 \cdot \text{gcd}(i, j) + 28$.

• Với truy vấn thứ nhất, các thành phố có thể đi đến được từ thành phố $20$ là $8, 20$.
• Với truy vấn thứ hai, thành phố duy nhất có thể đi đến được từ thành phố $26$ là $26$.
• Với truy vấn thứ ba, các thành phố có thể đi đến được từ thành phố $7$ là $7, 49$.
• Với truy vấn thứ tư, các thành phố có thể đi đến được từ thành phố $28$ là $28, 112$.

Dữ liệu vào 2

81781525 3945925
10
53907475
6160906250298067
3007621769603801
134161450
23675550
4034161385146811
2151358558435
12908151350610
112647860153451
9491287293575

Dữ liệu ra 2

53908389
6160906250298067
3007621769603801
9491260218029
2151369618045
4034161385146811
2151369618045
332851610359999
112647860153451
9491260218029

Phép XOR bit $x \oplus y$ của các số nguyên không âm $x, y$ được định nghĩa như sau:

• Trong biểu diễn nhị phân của $x \oplus y$, chữ số ở vị trí $2^k$ ($k \ge 0$) là $1$ khi và chỉ khi đúng một trong các chữ số ở vị trí $2^k$ trong biểu diễn nhị phân của $x$ và $y$ là $1$; ngược lại, nó là $0$.
• Ví dụ: $3 \oplus 5 = 6$ (trong hệ nhị phân, $011 \oplus 101 = 110$).