题目描述

你将得到四个正整数：$n, l, r, k$。

你的任务是构造一个 长度为 $n$ 的数组 $a$，使得满足以下条件：

1. 对于每个 $1 \leq i \leq n$，有：

   $$l \leq a_i \leq r$$

2. 数组的按位 与（AND）结果与按位 异或（XOR）结果相同：

   $$a_1 \& a_2 \& \dots \& a_n = a_1 \oplus a_2 \oplus \dots \oplus a_n $$

你的目标是找到满足以上条件的 字典序最小的数组 $a$。

• 如果不存在这样的数组，输出 -1。
• 如果存在，你只需要输出第 $k$ 项 $a_k$，而不是整个数组。

💡 字典序定义：

• 如果数组 $a$ 是数组 $b$ 的前缀且 $a \neq b$，那么 $a$ 的字典序更小；
• 否则，比较它们第一个不同位置的元素，较小的那一方字典序更小。

输入格式

• 第一行输入一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的组数。
• 每个测试用例占一行，包含四个正整数： $n, l, r, k$（$1 \leq k \leq n \leq 10^{18}$，$1 \leq l \leq r \leq 10^{18}$）

输出格式

对于每个测试用例，输出满足条件的数组的第 $k$ 项 $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

说明

样例解释

• 第 1 组：只有一个元素，数组为 $[4]$，满足条件。
• 第 2 组：最小字典序数组是 $[1,1,1]$，其按位与与按位异或都是 1。
• 第 3、4 组：数组可以为 $[6,6,8,8]$，满足条件。
• 第 5、6、7 组：无法构造出满足条件的数组，输出 $-1$。
• 第 8 组：数组全部为 $10^{18}$，满足条件。
• 第 9 组：字典序最小解是数组开头是 $1$ ，之后填 $2$ ，所以第 $10^{18}$ 项是 $2$ 。