有 $10^{16}$ 座城市,編號為 $1, 2, \dots, 10^{16}$。
對於唔同嘅城市 $i, j$,當且僅當 $\operatorname{lcm}(i, j) = A \cdot \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$ 之間存在道路嘅條件等價於 $\operatorname{lcm}(i, j) = 3 \cdot \gcd(i, j) + 28$。
- 對於第一個查詢,由城市 $20$ 可以到達嘅城市係 $8, 20$。
- 對於第二個查詢,由城市 $26$ 可以到達嘅唯一城市係 $26$。
- 對於第三個查詢,由城市 $7$ 可以到達嘅城市係 $7, 49$。
- 對於第四個查詢,由城市 $28$ 可以到達嘅城市係 $28, 112$。
非負整數 $x, y$ 嘅按位異或 $x \oplus y$ 定義如下:
- 喺 $x \oplus y$ 嘅二進制表示入面,$2^k$($k \ge 0$)位上面嘅數字係 $1$,當且僅當 $x$ 同 $y$ 嘅二進制表示喺 $2^k$ 位上面嘅數字恰好有一個係 $1$;否則係 $0$。
例如,$3 \oplus 5 = 6$(用二進制表示即係 $011 \oplus 101 = 110$)。