主宰。 - 失去梦想的壮举。
给你四个正整数 $$$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$$$。
示例
输入复制
91 4 4 13 1 3 34 6 9 24 6 9 34 6 7 42 5 5 12 3 6 2999999999999999999 1000000000000000000 1000000000000000000 9999999999999999991000000000000000000 1 999999999999999999 1000000000000000000
输出复制
4 1 6 8 -1 -1 -1 1000000000000000000 2
注意
在第一个测试用例中,数组 $$$a = [4]$$$。可以证明,不存在满足上述要求且字典顺序更小的数组。
在第二个测试用例中,数组 $$$a= [1,1,1]$$$。可以证明,不存在满足上述要求且字典顺序更小的数组。
在第三个测试用例和第四个测试用例中,数组 $$$a = [6,6,8,8]$$$。可以证明,不存在满足上述要求且字典顺序更小的数组。
在第五个测试用例和第六个测试用例中,可以证明不存在满足上述要求的数组。