SUMIJ

Problem

You are given an array consisting of N integers: ~A_1, A_2, \cdots, A_N~. We need to find two positions ~i~ and ~j~ in the array ~(1 \le i < j \le N)~, such that ~A_i + A_{i+1} + A_j = i + j~. If there are multiple pairs ~i~ and ~j~ that satisfy the above condition, we want the pair with the greatest difference ~j - i~. If there are multiple pairs with the same maximum difference, we want the one with the smallest value of ~i~.

Input Files:

The first line of the input will contain a positive integer ~T~, the number of queries. In each of the next ~T~ queries, the first line will contain a natural number ~N~, the number of elements in the array. The second line will contain exactly ~N~ integers ~A_1, A_2, \cdots, A_N~, separated in pairs by a single space.

Output Files:

The output should contain ~T~ lines. Each line should contain two numbers separated by a single space, indicating the requested positions ~i~ and ~j~ for the corresponding query. If no pair satisfies the conditions of the problem statement, the line should contain the word "IMPOSSIBLE".

Constraints

• ~1 \le T \le 5~
• ~1 \le N \le 1.000.000~, and the sum of ~N~ over all queries will not exceed ~2.000.000~
• ~-1000 \le A_i \le 1000~ for each ~i~

Example of Input - Output Files:

STDIN (oddsum.in)

3
10
5 2 8 3 3 5 1 8 5 7
11
1 7  7 1 -4 8 9 7 9 4 5
6
1 2 -2 5 2 4

STDOUT (oddsum.out)

6 8
IMPOSSIBLE
2 5

Explanation of the Example

In the first query, the only segment of the array that has the desired property is the one between positions ~i = 6~ and ~j = 8~, which has a sum of ~5 + 1 + 8 = 14 = i + j~. In the second query, no segment of the array has the desired property. Finally, in the third query, there are three segments of the array that have the desired property:

• for ~i = 1~ and ~j = 2~, it is ~1 + 2 = 3 = i + j~,
• for ~i = 2~ and ~j = 5~, it is ~2 - 2 + 5 + 2 = 7 = i + j~,
• for ~i = 3~ and ~j = 6~, it is ~-2 + 5 + 2 + 4 = 9 = i + j~.

Among the three, the first one has ~j - i = 1~, while the other two have ~j - i = 2~. Among the two with the maximum value of ~j - i~, the desired answer is the one with the smallest value of ~i~, which is ~i = 2~, ~j = 5~.

Notes

• For test cases worth 30%, of the total points, it will be \(Ν \le 1000\).
• For test cases worth 60%, of the total points, it will be \(Ν \le 10.000\). Maximum execution time: 1 sec.
  Maximum available memory: 64 MB.