33OJ
登录 注册

#P17731. [ICPC 2019 Xuzhou R] Cat

[ICPC 2019 Xuzhou R] Cat

题目描述

Yen-Jen 非常喜欢猫。

现在,有 101810^{18} 只猫排成一行,其中第 ii 只猫的代价 cic_i 等于 ii,第 ii 只猫的编号也等于 ii。

现在,Yen-Jen 想要购买编号连续的一些猫,但他只有 SS 元钱。为了购买编号为 x,x+1,⋯ ,y−1,yx, x+1, \cdots, y-1, y 的猫,他需要花费 x⊕(x+1)⊕⋯⊕(y−1)⊕yx \oplus (x+1) \oplus \cdots \oplus (y-1) \oplus y 元钱,其中 ⊕\oplus 表示按位异或运算符。

现在,他想向你提出 TT 个询问。在每个询问中,他拥有 SS 元钱,并且希望所买猫的编号落在区间 [L,R][L, R] 内。Yen-Jen 最多能买多少只猫?如果他一只猫也买不了,请输出 -1。

输入格式

第一行包含一个整数 TT,表示 Yen-Jen 想要向你发起的询问个数。

接下来 TT 行,每行描述一个询问。每行包含三个整数 L,R,SL, R, S,表示 Yen-Jen 拥有 SS 元钱,并且希望购买编号在 [L,R][L, R] 范围内的猫。

  • 1≤T≤5×1051 \le T \le 5 \times 10^5
  • 1≤L≤R≤10181 \le L \le R \le 10^{18}
  • 0≤S≤2×10180 \le S \le 2 \times 10^{18}

输出格式

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

2
1 1 0
2 2 2
-1
1

提示

翻译由 DeepSeek V4 Pro 完成