CF2119C.A Good Problem

Juggernaut. - Lost Dream feat.星名はる

给定四个正整数 $n$、$l$、$r$ 和 $k$，需要找到一个字典序最小的长度为 $n$ 的整数数组 $a$，满足以下条件：

• 对于每个 $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$，其中 $\&$ 表示按位与运算，$\oplus$ 表示按位异或运算。

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

数组 $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$ 如果没有数组满足条件。

• 在第一个测试用例中，数组 $a = [4]$。可以证明没有满足上述要求且字典序更小的数组。
• 在第二个测试用例中，数组 $a = [1, 1, 1]$。可以证明没有满足上述要求且字典序更小的数组。
• 在第三个和第四个测试用例中，数组 $a = [6, 6, 8, 8]$。可以证明没有满足上述要求且字典序更小的数组。
• 在第五个和第六个测试用例中，可以证明没有满足上述要求的数组。