F 1e16 Cities

問題

制限時間: 2 sec メモリ制限: 1024 MB

1e16 cities

Statement

\(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\) が与えられるので、都市 \(x_i\) から \(0\) 本以上の道を通ることで到達可能な都市すべての番号の総 (ビット単位) XOR を出力してください。

Input

\(1\) 行目に整数 \(A,B\) がこの順に空白区切りで与えられます。 (\(1\leq A,B \leq 10^8\))

\(2\) 行目に整数 \(Q\) が与えられます。 (\(1\leq Q\leq 10^5\))

続く \(Q\) 行のうち \(i\) 行目に、 \(i\) 番目のクエリでの \(x_i\) が整数として与えられます。 ( \(1\leq x_i\leq 10^{16}\) )

Output

\(Q\) 行出力してください。

\(i\ (1\leq i\leq Q)\) 行目には \(i\) 番目のクエリに対する答えを出力してください。

Examples

Input 1

Output 1

Input 2

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

Output 2

53908389
6160906250298067
3007621769603801
9491260218029
2151369618045
4034161385146811
2151369618045
332851610359999
112647860153451
9491260218029

Note

\(1\) つ目のサンプルについて、都市 \(i,j\) 間に道があることは \(\operatorname{lcm}(i,j)=3\cdot\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 \geq 0)\) の位の数は、\(x,y\) を二進表記した際の \(2^k\) の位の数のうち丁度一方が \(1\) であれば \(1\)、そうでなければ \(0\) である。

例えば、\(3 \oplus 5 = 6\) となります(二進表記すると \(011 \oplus 101 = 110\) )。

サンプル