← 返回题目列表

Codeforces · 2119/C

C. 一个好问题

中文机器翻译题面 查看原题

主宰。 - 失去梦想的壮举。

给你四个正整数 $$$n、l、r、k$$$。您需要找到按字典顺序最小的$$$^{\text{*}}$$$ 数组$$$a$$$,长度为$$$n$$$,由整数组成,这样:

  • 对于每个 $$$1 \leq i \leq n$$$,$$$l \leq a_i \leq r$$$。
  • $$$a_1 \, \& \, a_2 \, \& \, \ldots \, \& \, a_n = a_1 \oplus a_2 \oplus \ldots \oplus a_n$$$,其中 $$$\&$$$ 表示按位 AND 运算,$$$\oplus$$$ 表示按位 XOR 运算。

如果不存在这样的数组,则输出$$$-1$$$。否则,由于整个数组可能太大而无法输出,因此仅输出 $$$a_k$$$。

$$$^{\text{*}}$$$当且仅当满足以下条件之一时,数组 $$$a$$$ 按字典顺序小于数组 $$$b$$$:

  • $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;或
  • 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,数组 $$$a$$$ 的元素比 $$$b$$$ 中的相应元素小。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例包含四个正整数 $$$n,l,r,k$$$ ($$$1 \le k \le n \le 10^{18}$$$, $$$1 \le l \le r \le 10^{18}$$$)。

输出

对于每个测试用例,如果没有数组满足条件,则输出 $$$a_k$$$ 或 $$$-1$$$。

示例

输入
复制

9
1 4 4 1
3 1 3 3
4 6 9 2
4 6 9 3
4 6 7 4
2 5 5 1
2 3 6 2
999999999999999999 1000000000000000000 1000000000000000000 999999999999999999
1000000000000000000 1 999999999999999999 1000000000000000000

输出
复制

4
1
6
8
-1
-1
-1
1000000000000000000
2

注意

在第一个测试用例中,数组 $$$a = [4]$$$。可以证明,不存在满足上述要求且字典顺序更小的数组。

在第二个测试用例中,数组 $$$a= [1,1,1]$$$。可以证明,不存在满足上述要求且字典顺序更小的数组。

在第三个测试用例和第四个测试用例中,数组 $$$a = [6,6,8,8]$$$。可以证明,不存在满足上述要求且字典顺序更小的数组。

在第五个测试用例和第六个测试用例中,可以证明不存在满足上述要求的数组。