Twin Clusters
Contest: Codeforces Round 880 (Div. 1)
Difficulty rating: 2600
Tags: bitmasks, brute force, constructive algorithms, math, probabilities

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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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.

Example input:
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

Example output:
2 4 6 6
2 2 3 4
1 1 2 2
1 1 4 10

Editorial:
Deterministic solution:
Let us first look for segments that zeros first $$$k$$$ (out of $$$2k$$$) bits. Since we have $$$n = 2^{k + 1}$$$, then we have $$$n + 1$$$ prefix xors of the array (along with en empty prefix). Let us look at the xor prefix modulo $$$2^k$$$. Each time we have a prefix xor that has already occurred before let us match it with this previous occurrence. We will find at least $$$2^k + 1$$$ such segments. Note that segments have pairwise different ends and pairwise different beginnings.
Each of those segments generates some kind of xor value on the other $$$k$$$ bits. Since there is only $$$2^k$$$ different possible values, due to pigeon principle there will be two segments that generate same xor. We select those two intervals. If they are disjoint then we already found the answer. Otherwise the final answer will be the xor of those two segments (values that are covered only by one of them). It can be showed that we will obtain two disjoint, non-empty segments.
Nondeterministic solution:
If there are any duplicates in the array, then we can take two one-element arrays and obtain answer. From now on we will assume that no duplicates occur in the array.
Let us observe that number of valid segments is equal to $$${n \choose 2} + n \ge 2^{2k + 1}$$$ which is over twice larger than all possible xor values for a segment which is $$$2^{2k}$$$. This suggest, that chances of collision of two random segments is quite high. For simplicity let us assume there is exactly $$$2^{2k + 1}$$$ segments. Let us look at the final distribution over the xors used by segments. It can be showed by exchange argument, that the the distribution that needs the most random tosses to obtain collision is the one in which every xor value is used by exactly two segments. Since we choose segments randomly, by birthday paradox the expected time of obtaining a collision is around 2^k. Now there is a chance, that we will toss the same segment twice, but if we multiply the number of tossing by $$$\log(n)$$$ then chance that we find two different segments is very high (in reality even less random choices are necessary).
There is another issue, even if we find two different segments with the same xor values. They can use common elements. But then we can simply take only the elements that belong to the exactly one of them.
Still if the segments had common end one of the obtained segments would be empty. To omit this issue let us see that the second obtained segment would have xor equal to $$$0$$$. So now we can take any prefix and corresponding suffix as an answer. Unfortunately this segment can have length $$$1$$$. But in this case the only element in the segment has to be equal to $$$0$$$.
There must be at most one number $$$0$$$ in the array, so we can simply get rid of it (shorten the array by one). The analysis still holds (with some slight modifications).