310449: CF1835C. Twin Clusters

C. Twin Clusterstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Famous worldwide astrophysicist Mleil waGrasse Tysok recently read about the existence of twin galaxy clusters. Before he shares this knowledge with the broader audience in his podcast called S.tarT-ok, he wants to prove their presence on his own. Mleil is aware that the vastness of the universe is astounding (almost as astounding as his observation skills) and decides to try his luck and find some new pair of twin clusters.

To do so, he used his TLEscope to observe a part of the night sky that was not yet examined by humanity in which there are exactly $2^{k + 1}$ galaxies in a row. $i$-th of them consist of exactly $0 \le g_i < 4^k$ stars.

A galaxy cluster is any non-empty contiguous segment of galaxies. Moreover, its' trait is said to be equal to the bitwise XOR of all values $g_i$ within this range.

Two galaxy clusters are considered twins if and only if they have the same traits and their corresponding segments are disjoint.

Write a program that, for many scenarios, will read a description of a night sky part observed by Mleil and outputs a location of two intervals belonging to some twin clusters pair, or a single value $-1$ if no such pair exists.

Input

The first line contains a single integer $t$, denoting the number of test cases that the program has to handle. The following lines contain test case descriptions, each containing exactly two lines.

The first of them contains a single integer $k$ ($0 \le k \le 17$).

The second line contains $2^{k + 1}$ integers $g_1, g_2, \ldots, g_{2^{k+1}}$ ($0 \le g_i < 4^k$).

We guarantee that the sum of values $2^{k + 1}$ over all test cases does not exceed $2^{18}$.

Output

Answers for all test cases should be present in separate lines. If there exist a pair of twin galaxies, then output four integers $a$, $b$, $c$, and $d$ denoting their inclusive ranges $[a, b]$ and $[c, d]$ (the first interval does not need to start before the second one, but they have to be disjoint). If no pair of such galaxies exist, output a single value $-1$ instead.

ExampleInput

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

Output

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

Note

In the first test case we pick intervals $[2, 4]$ and $[6, 6]$ as our twin clusters. The trait of the first interval equals $15 \oplus 0 \oplus 7 = 8$, and the trait of the second interval equals $8$, so these galaxy clusters are indeed twins.

题目大意：
天体物理学家Mleil waGrasse Tysok想要在播客"S.tarT-ok"中分享关于双胞胎星系团（twin galaxy clusters）的知识，为此他需要自己证明它们的存在。他使用TLEscope观察到了一个由$2^{k+1}$个星系组成的夜空部分，每个星系包含$0 \le g_i < 4^k$颗星星。一个星系团是任意非空连续的星系段，其特征值是这些星系内所有$g_i$值的按位异或（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。

示例：
输入：
```
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
```
输出：
```
2 4 6 6
2 2 3 4
1 1 2 2
1 1 4 10
```题目大意： 天体物理学家Mleil waGrasse Tysok想要在播客"S.tarT-ok"中分享关于双胞胎星系团（twin galaxy clusters）的知识，为此他需要自己证明它们的存在。他使用TLEscope观察到了一个由$2^{k+1}$个星系组成的夜空部分，每个星系包含$0 \le g_i < 4^k$颗星星。一个星系团是任意非空连续的星系段，其特征值是这些星系内所有$g_i$值的按位异或（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。 示例： 输入： ``` 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 ``` 输出： ``` 2 4 6 6 2 2 3 4 1 1 2 2 1 1 4 10 ```