共有 $10^{16}$ 座城市，編號為 $1, 2, \dots, 10^{16}$。

對於相異的城市 $i, j$，若且唯若 $\text{lcm}(i, j) = A \cdot \text{gcd}(i, j) + B$ 時，城市 $i$ 與城市 $j$ 之間存在一條雙向道路。

請回答 $Q$ 筆詢問。在第 $i$ 筆詢問中，給定一個整數 $x_i$。請輸出所有能從城市 $x_i$ 透過零條或多條道路到達的城市編號之位元互斥或（bitwise XOR）總和。

輸入格式

第一行包含整數 $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, y$ 的位元互斥或 $x \oplus y$ 定義如下：

• 在 $x \oplus y$ 的二進位表示中，若且唯若 $x$ 與 $y$ 二進位表示中 $2^k$ ($k \ge 0$) 位上的數字恰有一個為 $1$ 時，該位上的數字為 $1$；否則為 $0$。

例如，$3 \oplus 5 = 6$（二進位下，$011 \oplus 101 = 110$）。