CF1835C Twin Clusters

著名的天体物理学家 Mleil waGrasse Tysok 最近读到关于孪生星系团存在的报道。在他打算在自己的播客 S.tarT-ok 上向广大听众分享这一知识之前，他想亲自证明它们的存在。Mleil 意识到宇宙的浩瀚令人惊叹（几乎和他的观察能力一样惊人），于是决定碰碰运气，寻找一对新的孪生星系团。 为此，他用他的 TLEscope 观测了人类尚未探索过的夜空区域，这一区域恰好有 $2^{k+1}$ 个星系排成一行。第 $i$ 个星系恰好包含 $0 \le g_i < 4^k$ 颗恒星。 一个星系团是指任意非空的连续星系区间。此外，它的“特征值”定义为该区间内所有 $g_i$ 的按位异或（bitwise XOR）结果。 如果两个星系团的特征值相同，且它们对应的区间没有重叠，则称它们为孪生星系团。 请编写程序，对于多个观测场景，读取 Mleil 观测到的夜空区域描述，输出某一对孪生星系团的两个区间的位置，或者如果不存在这样的孪生星系团，则输出 $-1$。

第一行包含一个整数 $t$，表示需要处理的测试用例数量。接下来的每组测试用例包含两行。 第一行包含一个整数 $k$（$0 \le k \le 17$）。 第二行包含 $2^{k+1}$ 个整数 $g_1, g_2, \ldots, g_{2^{k+1}}$（$0 \le g_i < 4^k$）。 保证所有测试用例中 $2^{k+1}$ 的总和不超过 $2^{18}$。

每个测试用例的答案输出一行。如果存在一对孪生星系团，则输出四个整数 $a$、$b$、$c$、$d$，表示它们的区间 $[a, b]$ 和 $[c, d]$（区间为闭区间，且两区间不重叠，区间顺序不限）。如果不存在这样的孪生星系团，则输出 $-1$。

在第一个测试用例中，我们可以选择区间 $[2, 4]$ 和 $[6, 6]$ 作为孪生星系团。第一个区间的特征值为 $15 \oplus 0 \oplus 7 = 8$，第二个区间的特征值为 $8$，因此这两个星系团确实是孪生的。 由 ChatGPT 4.1 翻译