有 $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
说明
对于第一个样例，城市 $i, j$ 之间存在道路的条件等价于 $\text{lcm}(i, j) = 3 \cdot \text{gcd}(i, j) + 28$。
- 对于第一个查询，从城市 20 可达的城市为 8, 20。
- 对于第二个查询，从城市 26 可达的唯一城市为 26。
- 对于第三个查询，从城市 7 可达的城市为 7, 49。
- 对于第四个查询，从城市 28 可达的城市为 28, 112。
输入格式 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
说明
非负整数 $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$）。