codeforces#P1416B. Make Them Equal
Make Them Equal
Description
You are given an array $a$ consisting of $n$ positive integers, numbered from $1$ to $n$. You can perform the following operation no more than $3n$ times:
- choose three integers $i$, $j$ and $x$ ($1 \le i, j \le n$; $0 \le x \le 10^9$);
- assign $a_i := a_i - x \cdot i$, $a_j := a_j + x \cdot i$.
After each operation, all elements of the array should be non-negative.
Can you find a sequence of no more than $3n$ operations after which all elements of the array are equal?
The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.
The first line of each test case contains one integer $n$ ($1 \le n \le 10^4$) — the number of elements in the array. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$) — the elements of the array.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^4$.
For each test case print the answer to it as follows:
- if there is no suitable sequence of operations, print $-1$;
- otherwise, print one integer $k$ ($0 \le k \le 3n$) — the number of operations in the sequence. Then print $k$ lines, the $m$-th of which should contain three integers $i$, $j$ and $x$ ($1 \le i, j \le n$; $0 \le x \le 10^9$) for the $m$-th operation.
If there are multiple suitable sequences of operations, print any of them. Note that you don't have to minimize $k$.
Input
The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.
The first line of each test case contains one integer $n$ ($1 \le n \le 10^4$) — the number of elements in the array. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$) — the elements of the array.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^4$.
Output
For each test case print the answer to it as follows:
- if there is no suitable sequence of operations, print $-1$;
- otherwise, print one integer $k$ ($0 \le k \le 3n$) — the number of operations in the sequence. Then print $k$ lines, the $m$-th of which should contain three integers $i$, $j$ and $x$ ($1 \le i, j \le n$; $0 \le x \le 10^9$) for the $m$-th operation.
If there are multiple suitable sequences of operations, print any of them. Note that you don't have to minimize $k$.
Samples
3
4
2 16 4 18
6
1 2 3 4 5 6
5
11 19 1 1 3
2
4 1 2
2 3 3
-1
4
1 2 4
2 4 5
2 3 3
4 5 1