P17731 [ICPC 2019 Xuzhou R] Cat

Yen-Jen 非常喜欢猫。 现在，有 $10^{18}$ 只猫排成一行，其中第 $i$ 只猫的代价 $c_i$ 等于 $i$，第 $i$ 只猫的编号也等于 $i$。 现在，Yen-Jen 想要购买编号连续的一些猫，但他只有 $S$ 元钱。为了购买编号为 $x, x+1, \cdots, y-1, y$ 的猫，他需要花费 $x \oplus (x+1) \oplus \cdots \oplus (y-1) \oplus y$ 元钱，其中 $\oplus$ 表示按位异或运算符。 现在，他想向你提出 $T$ 个询问。在每个询问中，他拥有 $S$ 元钱，并且希望所买猫的编号落在区间 $[L, R]$ 内。Yen-Jen 最多能买多少只猫？如果他一只猫也买不了，请输出 `-1`。

第一行包含一个整数 $T$，表示 Yen-Jen 想要向你发起的询问个数。 接下来 $T$ 行，每行描述一个询问。每行包含三个整数 $L, R, S$，表示 Yen-Jen 拥有 $S$ 元钱，并且希望购买编号在 $[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}$

对于每个询问，输出 Yen-Jen 能够购买的最大猫的数量。如果 Yen-Jen 一只猫也买不了，则输出 `-1`。

翻译由 DeepSeek V4 Pro 完成