XOR

XOR, also known as Exclusive OR, is a logical operation often used in programming. It is referred to $\oplus$, but in programming, for simplicity, it is referred to as $^$.

There are many special propreties about XOR:

The order in which you calculate XOR operations does not matter, for example, $2^3^1^4$ can also be calculated as $1^2^4^2$.

If you have some numbers, divide them into any number of groups, and find their XOR’s in each group, and find the total sum:

You can find a max or a min answer, the max answer is if you added them all (we split each number as an individual group), and the min answer is if you didn’t split anything and XOR’d it all.

Additionally, if you had two numbers $L$ and $R$, and wanted to find their XOR from L to R, inclusive: meaning, for example, if L were 2 and R were 5, you’d have to find $2^3^4^5$.

If you implemented this in coding, you could get TLE due to large inputs. It could, however, be fixed with this proprety:

$XOR(L to R)=XOR(0 to R)⊕XOR(0 to L−1)$

That does not sound very time-efficient, right?

The key XOR property of consecutive numbers is about how XOR behaves over ranges like$$0 \oplus 1 \oplus 2 \oplus \cdots \oplus n$$This pattern repeats every 4 numbers:$$\begin{aligned} \text{If } n \bmod 4 = 0 &\Rightarrow \text{result} = n \\ \text{If } n \bmod 4 = 1 &\Rightarrow \text{result} = 1 \\ \text{If } n \bmod 4 = 2 &\Rightarrow \text{result} = n + 1 \\ \text{If } n \bmod 4 = 3 &\Rightarrow \text{result} = 0 \end{aligned}$$

P.S. if you have no idea why you’re WA’ing, did you use long long int?