← 返回题目列表

Codeforces · 1835/C

C. 双簇

中文机器翻译题面 查看原题

全球著名天体物理学家 Mleil waGrasse Tysok 最近了解到双星系团的存在。在他在名为 S.tarT-ok 的播客中与更广泛的受众分享这些知识之前,他想证明自己的存在。姆莱尔意识到宇宙的浩瀚令人震惊(几乎和他的观察能力一样令人震惊),并决定碰碰运气,找到一对新的双星团。

为此,他使用 TLEscope 观察了人类尚未检查过的夜空部分,其中恰好存在连续的 $$$2^{k + 1}$$$ 星系。其中 $$$i$$$ 恰好由 $$$0 \le g_i < 4^k$$$ 颗星组成。

星系团是星系的任何非空连续部分。此外,它的特征据说等于该范围内所有值 $$$g_i$$$ 的按位异或。

两个星系团被认为是双胞胎当且仅当它们具有相同的特征并且它们对应的部分不相交。

编写一个程序,在许多情况下,将读取 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$$$。

示例

输入 #1

4
2
4 15 0 7 11 8 3 2
1
0 1 2 3
0
0 0
3
15 63 57 39 61 25 42 61 50 41 27 41 56 23 17 27

输出 #1

2 4 6 6
2 2 3 4
1 1 2 2
1 1 4 10

注意

在第一个测试用例中,我们选择区间 $$$[2, 4]$$$ 和 $$$[6, 6]$$$ 作为我们的孪生簇。第一个区间的特征等于 $$$15 \oplus 0 \oplus 7 = 8$$$,第二个区间的特征等于 $$$8$$$,所以这些星系团确实是双胞胎。