Fiboxor

Little Square and Little Triangle are fighting again on Valentine's day. The reason for this year's fight: Little Square claimed that the Fibonacci sequence is far prettier than the sequence of powers of two, which is Little Triangle's favorite.

The Fibonacci sequence starts with 0 and 1, and each later element is the sum of the two elements before it:

$0, 1, 1, 2, 3, 5, 8, 13, \dots$

Little Triangle likes this sequence because the bitwise exclusive or (XOR) of any subarray is easy to compute. Little Triangle said that if Little Square answers $Q$ XOR subarray queries correctly, they will accept that Fibonacci is better. Because the Fibonacci numbers grow exponentially, Little Triangle agreed to accept only the value of each subarray XOR modulo $2^k$.

Each of the $Q$ queries gives three integers $k$, $l$, $r$. For each query, compute the XOR of the Fibonacci numbers with indexes in the interval $[l, r]$ (both ends included, indexed from $0$), modulo $2^k$.

• $1 \le Q \le 10^6$
• $0 \le l \le r \le 10^{18}$
• $1 \le k \le 20$

Let $a \oplus b$ denote the XOR of $a$ and $b$.

In the first query, $0 \oplus 1 \oplus 1 \oplus 2 \mod 2^2 = 2 \mod 4 = 2$.

In the second query, $3 \oplus 5 \oplus 8 \mod 2^4 = 14 \mod 16 = 14$.