Differential Sorting solution codeforces

Differential Sorting solution codeforces

 

You are given an array aa of nn elements.

Your can perform the following operation no more than nn times: Select three indices x,y,zx,y,z (1x<y<zn)(1≤x<y<z≤n) and replace axax with ayazay−az. After the operation, |ax||ax| need to be less than 10181018.

Your goal is to make the resulting array non-decreasing. If there are multiple solutions, you can output any. If it is impossible to achieve, you should report it as well.

Input

Each test contains multiple test cases. The first line will contain a single integer tt (1t10000)(1≤t≤10000) — the number of test cases. Then tt test cases follow.

The first line of each test case contains a single integer nn (3n2105)(3≤n≤2⋅105) — the size of the array aa.

The second line of each test case contains nn integers a1,a2,,ana1,a2,…,an (109ai109)(−109≤ai≤109), the elements of aa.

It is guaranteed that the sum of nn over all test cases does not exceed 21052⋅105.

Output

For each test case, print 1−1 in a single line if there is no solution. Otherwise in the first line you should print a single integer mm (0mn)(0≤m≤n) — number of operations you performed.

Then the ii-th of the following mm lines should contain three integers x,y,zx,y,z (1x<y<zn)(1≤x<y<z≤n)— description of the ii-th operation.

If there are multiple solutions, you can output any. Note that you don’t have to minimize the number of operations in this task.

Example
input

Copy
3
5
5 -4 2 -1 2
3
4 3 2
3
-3 -2 -1
output

Copy
2
1 2 3
3 4 5
-1
0
Note

In the first example, the array becomes

[6,4,2,1,2][−6,−4,2,−1,2] after the first operation,

[6,4,3,1,2][−6,−4,−3,−1,2] after the second operation.

In the second example, it is impossible to make the array sorted after any sequence of operations.

In the third example, the array is already sorted, so we don’t need to perform any operations.

Leave a Comment

Your email address will not be published.