CF1416B Make Them Equal

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≤i,j≤n; 0≤x≤10^9)$ ;
assign $a_i:=a_i−x⋅i$ , $a_j:=a_j+x⋅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?

Input

The first line contains one integer $t$ ( $1≤t≤10^4$ ) — the number of test cases. Then $t$ test cases follow.
The first line of each test case contains one integer $n$ ( $1≤n≤10^4$ ) — the number of elements in the array. The second line contains $n$ integers $a_1,a_2,\cdots,a_n$ ( $1≤a_i≤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≤k≤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≤i,j≤n$ , $0≤x≤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$ .

Example

input

3
4
2 16 4 18
6
1 2 3 4 5 6
5
11 19 1 1 3

output

Idea

对于 $a_i:=a_i−x⋅i$ , $a_j:=a_j+x⋅i$ ，取 $i=1$ ，则 $a_1:=a_1-x$ ， $a_j:=a_j+x$ ；取 $j=1$ ，则 $a_1:=a_1+x\cdot i$ ， $a_i:=a_i-x\cdot i$ 。
可以从 $a_1$ 中取出任何数字补充到 $a_j$ 上，也可以从 $a_i$ 中取出 $i$ 的倍数补充到 $a_1$ 上。
不妨考虑首先将序列 $a$ 的和全部堆在 $a_1$ 上。若 $i\mid a_i$ ，那么就取 $x=\frac{a_i}{i}$ ，操作完成后， $a_1:=a_1+a_i$ ， $a_i=0$ 。若 $i\not\mid a_i$ ，那么取 $x=i-(a_i\bmod i)$ ，操作完成后， $a_1:=a_1-i+(a_i\bmod i)$ ， $a_i:=a_i+i-(a_i\bmod i)$ ，这时候就有 $a_i\mid i$ 。至多经过 $2(n-1)$ 次操作， $a_1:=\sum\limits_{i=1}^n a_i$ ，除 $a_1$ 外，其余元素都为 $0$ 。
最后经过 $n$ 次操作，将 $\frac{\sum\limits_{i=1}^n a_i}{n}$ 分配到其余各个元素。当 $n\not\mid\sum\limits_{i=1}^n a_i$ 时，不能完成操作。

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: CF1416B
Date: 9/28/2020
Description:  Constructive Algorithms
*******************************************************************/
#include<iostream>
#include<utility>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int N=10005;
int _;
int n;
ll a[N];
vector<pair<pair<int,int>,ll>>ans;
int main(){
	for(cin>>_;_;_--){
		ans.clear();
		scanf("%d",&n);
		int i;
		ll sum=0;
		for(i=1;i<=n;i++){
			scanf("%lld",&a[i]);
			sum+=a[i];
		}
		if(sum%n){
			puts("-1");
			continue;
		}
		for(i=2;i<=n;i++){
			if(a[i]%i){
				ans.push_back(make_pair(make_pair(1,i),i-a[i]%i));
				a[i]+=i-a[i]%i;
			}
			ans.push_back(make_pair(make_pair(i,1),a[i]/i));
		}
		for(i=2;i<=n;i++){
			ans.push_back(make_pair(make_pair(1,i),sum/n));
		}
		printf("%d\n",ans.size());
		for(i=0;i<ans.size();i++){
			printf("%d %d %d\n",ans[i].first.first,ans[i].first.second,ans[i].second);
		}
	}
	return 0;
}