Alexey Yurievich and Mikhail Leonidovich went by train to Troitsk. On the way, a shift worker and a demobilization sat down next to them. After getting to know each other and short stories about themselves, the shift worker and the demobilized team decided to give Alexey Yuryevich and Mikhail Leonidovich a “man” test: they need to solve a difficult programming problem.
Help Aleksey Yuryevich and Mikhail Leonidovich pass the "man" test.
Given an array of integers a
1,a
2,...,a
n.
The cost of an array subsegment 1 <= l <= r <= n is the value f(l,r) = sum(l,r) − xor(l,r), where sum(l,r) = a
l +a
l+1+...+a
r , and xor(l,r) = a
l ⊕a
l+1 ⊕...⊕a
r (⊕ here denotes the XOR operation, the bitwise XOR of numbers, see the Remark section for more details.
It is required to find a subsegment of the given array with the maximum value f(l,r). If there are several answers, then among them you need to find a subsegment with the minimum length, that is, the minimum value of r − +1.
Input
Each test consists of several sets of input data. The first line contains the integer t (1 <= t <= 10
4) — the number of test cases. The following is a description of the input data sets.
The first line of each test case contains a single integer n (1 <= n <= 10
5) — the length of the array.
The second line of each test case contains n integers a
1,a
2,...,a
n (0 <= a
i <= 10
9) — array elements.
It is guaranteed that the sum of n over all test cases does not exceed 2 · 10
5.
Imprint
For each test case, print two numbers 1 <= l <= r <= n such that the value f(l,r) is maximum over all subsegments of array a, and the length r −l +1 is minimum . If there are several correct answers, print any of them.
Examples
| # |
Input |
Output |
| 1 |
6
1
0
2
5 10
3
0 2 4
4
0 12 8 3
5
21 32 32 32 10
7
0 1 0 1 0 1 0
| 1 1
2 2
3 3
23
34
4 6 |
Remark
The XOR operation of two numbers a and b — it is a bitwise operation that is applied independently to each pair of corresponding bits a and b. This operation is modulo 2 addition. Here is its truth table for a pair of bits:
| a |
b |
a⊕b |
| 0 |
0 |
0 |
| 0 |
1 |
1 |
| 1 |
0 |
1 |
| 1 |
1 |
0 |
In the first test case f(1,1) = 1 − 1 = 0.
In Second set input data f(2,2) = 10 − 10 = 0. Note that that f(1,2) = (10 + 5) − (10 ⊕ 5) = 0, but among the maximum values of f(l,r) we need to find a subsegment with a minimum length.
In the fourth test case f(2,3) = (12+8) − (12 & 8) = 16.
The fifth test case has two correct answers, since f(2,3) = f(3,4) and their lengths are equal.