给定 $n, l, r, k$（$1 \le k \le n \le 10^{18}$，$1 \le l \le r \le 10^{18}$），要求构造长度为 $n$ 的数组 $a$，满足：

1. $l \le a_i \le r$；
2. $a_1 \& a_2 \& \dots \& a_n = a_1 \oplus a_2 \oplus \dots \oplus a_n$；

在所有合法数组中，输出字典序最小的数组的第 $k$ 个元素，不存在输出 $-1$。

---

条件分析

设

$$A = a_1 \& a_2 \& \dots \& a_n$$ $$X = a_1 \oplus a_oplus \dots \oplus a_n$$

已知 $A = X$。

按位分析

考虑某一位（二进制位）：

• 如果这一位所有数的 AND = $1$，则所有数该位都是 $1$，且 $n$ 必须为奇数（否则 XOR 该位 = $0$，矛盾）。
• 如果这一位所有数的 AND = $0$，则至少有一个数该位为 $0$，且 XOR 该位必须为 $0$ → 该位为 $1$ 的个数为偶数。

从整体看：

---

结论 1：$n$ 为奇数

设 $v = A = X$。
那么所有数在 $v$ 的 $1$ 位上全是 $1$。
在 $v$ 的 $0$ 位上，这些位在数组中的出现次数为偶数（这样才能 XOR = $0$），且至少有一个 $0$（保证 AND 该位 = $0$）。
一个简单的构造方法是：让所有数相等，且等于 $v$。

• $v$ 的 $1$ 位当然全 $1$（所有数在该位 = $1$）
• $v$ 的 $0$ 位在该数组全为 $0$（出现次数 $n$，$n$ 奇数 → 出现次数为奇数，不是偶数！等等，这有问题）

检查：如果全为 $v$，$v$ 某位为 $0$，那么所有数该位 = $0$，1 的个数 = $0$（偶数）✅，AND 该位 = $0$✅。所以全相同数可行。

再验证 AND 和 XOR：

• AND：所有数相同 = $v$ ⇒ AND = $v$
• XOR：$n$ 个数相同，$n$ 为奇数 ⇒ XOR = $v$（因为 $v \oplus v \oplus \dots \oplus v = v$ 当 $n$ 奇）。

所以确实成立。
且 $a_1$ 要最小 → $a_1 = l$ 即可，全数组为 $l$。

结论：$n$ 为奇数时，数组取 $[l, l, \dots, l]$ 即可。
所以 $a_k = l$。

---

结论 2：$n$ 为偶数

此时，从按位分析：

不能出现某位全 $1$（否则 AND = $1$，XOR = $0$ 矛盾）。
所以至少存在一个数在某位为 $0$ ⇒ AND = $0$。
要满足 AND = XOR ⇒ XOR = $0$。

等价条件：

• 数组中所有数的 AND = $0$（即对每一位，至少有一个数该位为 $0$）。
• 整个数组的 XOR = $0$（即对每一位，1 的个数为偶数）。

因为 $n$ 是偶数，一组可行构造是：取两个数 $x$ 和 $y$，每个出现 $\frac{n}{2}$ 次。

• AND = $x \& y$（因为每位的出现模式是 $x$ 和 $y$ 交叉）
• XOR = $0$（因为 XOR 相同值偶数次 = $0$，再加上两数 XOR 重复的抵消）

具体：
若数组由 $\frac{n}{2}$ 个 $x$ 和 $\frac{n}{2}$ 个 $y$ 组成，则 XOR = $x \oplus y$ 的出现次数为偶数？不对，
XOR = $(x \oplus x \oplus \dots \oplus x)$ [$\frac{n}{2}$ 次] $\oplus$ ($y \oplus \dots \oplus y$) [$\frac{n}{2}$ 次]
偶数次相同数 XOR = $0$，所以整体 XOR = $0$✅

AND = $x \& y$（因为对每一位：只有 $x$ 和 $y$ 同时为 1 时 AND 才为 1）

所以我们需要 $x \& y = 0$（这样 AND = $0$ = XOR）。
并且 $l \le x \le y \le r$。

为了字典序最小，我们把两个 $x$ 放在前面（索引 $1,2$ 为 $x$），后面 $y$ 放在索引 $3..n$（中间有偶数个，所以 $n \ge 4$ 需要）。

---

字典序最小构造

取 $x = l$，需要找一个 $y$ 在 $[l, r]$ 中，使得 $l \& y = 0$（AND 条件），并尽量小（这样 $a_3 = y$ 最小）。

如果 $l = 0$，那么 $x=0$，$y$ 可以选任意数，选最小的 $y = l = 0$，那么全数组为 $0$ ✅（$0 \& 0 = 0$，XOR=0）。

如果 $l > 0$，则找最小的 $y \ge l$ 使 $l \& y = 0$。
这个 $y$ 可以用：

• 对 $l$ 逐位，找到一个更高位的 1 跳过重叠。
• 简单方法：$y = (l$ 去掉所有 1 位的下一个值)。

更简单且保证能找到的是： 枚举 $l$ 到 $\min(l+1000, r)$（因为 $l$ 和 $y$ 在低位无公共 1 时，$y$ 不会太远，若 $r-l$ 很大，可能的 $y$ 是 $2^{\lfloor \log_2(l) \rfloor+1}$ 的幂次）。

所以算法：

1. 若 $l=0$ ⇒ $a_k = 0$（全 0 数组）。
2. 否则尝试 $p = l$ 到 $\min(l+1000, r)$ 找 $p \& l = 0$。
3. 若没找到，取 $highest = 2^{\lfloor \log_2(l) \rfloor+1}$（最小的比 $l$ 大的 2 的幂），若 $highest \le r$ 则 $y=highest$。
4. 若没找到 ⇒ $-1$。
5. 找到 $y$ 后，输出 $a_k$：
   $k=1$ 或 $k=2$ ⇒ $l$
   否则 ⇒ $y$。

---

时间复杂度

• $n$ 奇数：O(1)
• $n$ 偶数：O(1) 或 O(log r)（找最高位）
• 通过 $t \le 10^4$。

---

最终答案规律

• $n$ 奇数：输出 $l$。
• $n$ 偶数且 $l=0$：输出 $0$。
• $n$ 偶数且 $l>0$：
  • 若存在 $y \in [l, r]$ 使 $l \& y = 0$，取最小的 $y$
    输出：$k \le 2$ 时输出 $l$，否则输出 $y$。
  • 否则输出 $-1$。