$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$에서 0개 이상의 도로를 거쳐 도달할 수 있는 모든 도시 번호들의 비트 단위 XOR 합을 출력하십시오.

입력

첫 번째 줄에는 정수 $A, B$가 공백으로 구분되어 주어집니다. ($1 \le A, B \le 10^8$)

두 번째 줄에는 정수 $Q$가 주어집니다. ($1 \le Q \le 10^5$)

이어지는 $Q$개의 줄에는 각 쿼리에 대한 정수 $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

참고

첫 번째 예제에서, 도시 $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$의 비트 단위 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$).