33OJ
登录 注册

#P17731. [ICPC 2019 Xuzhou R] Cat

[ICPC 2019 Xuzhou R] Cat

Problem Description

Yen-Jen loves cat very much.

Now, there are 101810^{18} cats standing in a line, the ithi^{th} cat's cost value cic_i is equal to ii, the ithi^{th} cat's index is also equal to ii.

Now, Yen-Jen wants to buy some cats with continuous index, but he only has SS dollars. He wants to buy some cats with continuous indices. In order to buy cat with index x,x+1,⋯ ,y−1,yx, 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 TT questions. In each question, he has SS dollars, and he wants the indices of cats in range [L,R][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.

Input Format

The first line of the input file contains one integer TT denotes the number of questions that Yen-Jen wants to challenge you.

Then, in the next TT lines, each line contains one question. In each line, there are three integers L,R,SL, R, S, which means that Yen-Jen has SS dollars, and he wants to buy cats whose indices are in the range [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}

Output Format

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.

2
1 1 0
2 2 2
-1
1