P17731 [ICPC 2019 Xuzhou R] Cat

Yen-Jen loves cat very much. Now, there are $10^{18}$ cats standing in a line, the $i^{th}$ cat's cost value $c_i$ is equal to $i$, the $i^{th}$ cat's index is also equal to $i$. Now, Yen-Jen wants to buy some cats with continuous index, but he only has $S$ dollars. He wants to buy some cats with continuous indices. In order to buy cat with index $x, x + 1, \cdots, y - 1, y$, he needs to spend $x \oplus (x + 1) \oplus \cdots \oplus (y - 1) \oplus y$ dollars. $\oplus$ is the bitwise exclusive-or operator. Now, he wants to ask you $T$ questions. In each question, he has $S$ dollars, and he wants the indices of cats in range $[L, R]$. What's the maximum number of cat that Yen-Jen can buy? If he can't buy any cat, please report `-1` instead.

The first line of the input file contains one integer $T$ denotes the number of questions that Yen-Jen wants to challenge you. Then, in the next $T$ lines, each line contains one question. In each line, there are three integers $L, R, S$, which means that Yen-Jen has $S$ dollars, and he wants to buy cats whose indices are in the range $[L, R]$. - $1 \le T \le 5 \times 10^5$ - $1 \le L \le R \le 10^{18}$ - $0 \le S \le 2 \times 10^{18}$

In each question, output the maximum number of cats that Yen-Jen can buy. If Yen-Jen can't buy any cats, output `-1` instead.