$10^{16}$ 個の都市があり、それぞれ $1, 2, \dots, 10^{16}$ とラベル付けされています。

異なる2つの都市 $i, j$ について、$\text{lcm}(i, j) = A \cdot \text{gcd}(i, j) + B$ が成り立つ場合に限り、都市 $i$ と都市 $j$ の間に双方向の道路が存在します。

$Q$ 個のクエリに答えてください。 $i$ 番目のクエリでは、整数 $x_i$ が与えられます。都市 $x_i$ から道路を0回以上通って到達可能なすべての都市のラベルのビット単位のXOR（排他的論理和）を出力してください。

入力

1行目には、整数 $A, B$ がこの順にスペース区切りで与えられます。($1 \le A, B \le 10^8$) 2行目には、整数 $Q$ が与えられます。($1 \le Q \le 10^5$) 続く $Q$ 行の各行には、$i$ 番目のクエリに対する整数 $x_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$ と同値です。

• 1番目のクエリについて、都市 20 から到達可能な都市は 8, 20 です。
• 2番目のクエリについて、都市 26 から到達可能な都市は 26 のみです。
• 3番目のクエリについて、都市 7 から到達可能な都市は 7, 49 です。
• 4番目のクエリについて、都市 28 から到達可能な都市は 28, 112 です。

非負整数 $x, y$ のビット単位のXOR $x \oplus y$ は以下のように定義されます。

• $x \oplus y$ の二進表現において、$2^k$ ($k \ge 0$) の位の数字は、$x$ と $y$ の二進表現における $2^k$ の位の数字のうち、ちょうど一方が 1 である場合に 1 となり、それ以外の場合は 0 となります。

例えば、$3 \oplus 5 = 6$ です（二進数では $011 \oplus 101 = 110$）。