$1, 2, \dots, 10^{16}$ деп нөмірленген $10^{16}$ қала бар.
Әртүрлі $i, j$ қалалары үшін $i$ қаласы мен $j$ қаласының арасында екі бағытты жол тек $\operatorname{lcm}(i, j) = A \cdot \gcd(i, j) + B$ болған жағдайда ғана болады.
$Q$ сұранысқа жауап беріңіз.
$i$-ші сұраныста бүтін $x_i$ саны беріледі. $x_i$ қаласынан нөл немесе одан да көп жолдар арқылы жетуге болатын барлық қалалардың нөмірлерінің бит бойынша XOR мәнін шығарыңыз.
Кіріс деректері
Бірінші жолда бос орын арқылы осы ретпен $A, B$ бүтін сандары берілген. ($1 \le A, B \le 10^8$)
Екінші жолда бүтін $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$ қалаларының арасында жолдың болуы $\operatorname{lcm}(i, j) = 3 \cdot \gcd(i, j) + 28$ шартына пара-пар.
- Бірінші сұраныс үшін $20$ қаласынан жетуге болатын қалалар: $8, 20$.
- Екінші сұраныс үшін $26$ қаласынан жетуге болатын жалғыз қала: $26$.
- Үшінші сұраныс үшін $7$ қаласынан жетуге болатын қалалар: $7, 49$.
- Төртінші сұраныс үшін $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$).