XORificator 3000
Contest: Codeforces Round 984 (Div. 3)
Difficulty rating: 1900
Tags: bitmasks, dp, number theory, two pointers

Alice has been giving gifts to Bob for many years, and she knows that what he enjoys the most is performing bitwise XOR of interesting integers. Bob considers a positive integer $$$x$$$ to be interesting if it satisfies $$$x \not\equiv k (\bmod 2^i)$$$. Therefore, this year for his birthday, she gifted him a super-powerful "XORificator 3000", the latest model.

Bob was very pleased with the gift, as it allowed him to instantly compute the XOR of all interesting integers in any range from $$$l$$$ to $$$r$$$, inclusive. After all, what else does a person need for happiness? Unfortunately, the device was so powerful that at one point it performed XOR with itself and disappeared. Bob was very upset, and to cheer him up, Alice asked you to write your version of the "XORificator".

Input format:
The first line of input contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ — the number of XOR queries on the segment. The following $$$t$$$ lines contain the queries, each consisting of the integers $$$l$$$, $$$r$$$, $$$i$$$, $$$k$$$ $$$(1 \leq l \leq r \leq 10^{18}$$$, $$$0 \leq i \leq 30$$$, $$$0 \leq k < 2^i)$$$.

Output format:
For each query, output a single integer — the XOR of all integers $$$x$$$ in the range $$$[l, r]$$$ such that $$$x \not\equiv k \mod 2^i$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first query, the interesting integers in the range $$$[1, 3]$$$ are $$$1$$$ and $$$3$$$, so the answer will be $$$1 \oplus 3 = 2$$$.

Example input:
6
1 3 1 0
2 28 3 7
15 43 1 0
57 2007 1 0
1010 1993 2 2
1 1000000000 30 1543

Example output:
2
2
13
0
4
1000000519

Editorial:
Введём обозначение $$$XOR(l, r) = l \oplus (l+1) \oplus \dots \oplus r$$$ .
Первое, что приходит в голову при прочтении условия, это что мы можем вычислить $$$XOR$$$ всех чисел на отрезке $$$(0, x)$$$ за $$$O(1)$$$ по следующей формуле:
$$$$$$ \text{XOR}(0, x) = \begin{cases} x & \text{если } x \equiv 0 \pmod{4} \\ 1 & \text{если } x \equiv 1 \pmod{4} \\ x + 1 & \text{если } x \equiv 2 \pmod{4} \\ 0 & \text{если } x \equiv 3 \pmod{4} \end{cases} $$$$$$
Тогда $$$XOR(l, r)$$$ можно найти как $$$XOR(0, r) \oplus XOR(0, l-1)$$$.
Теперь заметим, что для ответа нам достаточно научиться за $$$O(1)$$$ находить $$$XOR$$$ всех неинтересных на отрезке: тогда мы сможем сделать $$$XOR$$$ со всем отрезком и получить $$$XOR$$$ уже всех интересных чисел.
Основание модуля, равное степени двойки, выбрано не случайно: нам достаточно «сжать» $$$l$$$ и $$$r$$$ в $$$2^i$$$ раз таким образом, чтобы в полученном диапазоне лежали все неинтересные числа, сдвинутые на $$$i$$$ битов право. Тогда вычислив $$$XOR(l', r')$$$ мы получим в точности искомый $$$XOR$$$ нечётных, также сдвинутый на $$$i$$$ битов вправо. Тогда, чтобы найти эти оставшиеся младшие $$$i$$$ битов, нам достаточно найти количество неинтересных чисел на отрезке $$$[l, r]$$$. Если оно будет нечётным, эти $$$i$$$ битов будут равны $$$k$$$, поскольку все они равны $$$k \mod 2^i$$$, а значит имеют одинаковые $$$i$$$ младших битов, равные собственно $$$k$$$, а значит их $$$XOR$$$ нечетное число раз будет также равен $$$k$$$. В противном случае младшие $$$i$$$ битов ответа будут равны $$$0$$$, так как мы сделали $$$XOR$$$ чётное число раз. Количество неинтересных чисел на отрезке можно вычислим похожим с $$$XOR(l, r)$$$ способом, а именно найти их количество на отрезках $$$[0, r]$$$ и $$$[0, l-1]$$$ и вычесть второе из первого. Количество чисел, равных $$$k$$$ оп модулю $$$m$$$ и не превышающих $$$r$$$ вычисляется как $$$\left\lfloor \frac{r - k}{m} \right\rfloor$$$.
Сложность решения по времени — $$$O(\mathit{\log r})$$$.