C. 一个好问题
每个测试的时间限制：2 秒
内存限制：256 兆字节

你会得到四个正整数 $n, l, r, k$。
你需要找到字典序最小的* 数组 $a$，长度为 $n$，由整数组成，满足：

• 对于每个 $1 \le i \le n$，有 $l \le a_i \le r$。
• $a_1 \& a_2 \& \dots \& a_n = a_1 \oplus a_2 \oplus \dots \oplus a_n$，
  其中 $\&$ 表示按位与运算，$\oplus$ 表示按位异或运算。

如果不存在这样的数组，输出 $-1$。
否则，由于整个数组可能太大，无法全部输出，只输出 $a_k$。

*字典序定义：
数组 $a$ 在字典序上比数组 $b$ 小，当且仅当以下之一成立：

• $a$ 是 $b$ 的前缀，但 $a \neq 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]$。可以证明没有更小的字典序数组满足条件。
• 在第五和第六个测试用例中，可以证明没有满足条件的数组。