Make Them Equal

题意翻译

- 给出一个序列 $a$，求出一个长度不超过 $3n$ 的操作序列，使序列 $a$ 中每个元素相等。 - 定义一次操作为：选出 $(i,j,x)$ 三元组，满足 $i,j$ 为序列合法下标，$x$ 为 $10^9$ 以内非负整数，令 $a_i:= a_i-x\cdot i,a_j:=a_j+x\cdot i$。 - 必须保证操作过程中的任意时刻序列 $a$ 中每个元素都非负。 - 输出时先输出操作次数 $k$，然后输出 $k$ 行操作序列。 - 数据组数 $t\le10^4$，序列长度 $n\le10^4$，元素大小 $1\le a_i\le10^5$。

题目描述

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: 1. choose three integers $ i $ , $ j $ and $ x $ ( $ 1 \le i, j \le n $ ; $ 0 \le x \le 10^9 $ ); 2. 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 $ .

输入输出样例

输入样例 #1

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

输出样例 #1

2
4 1 2
2 3 3
-1
4
1 2 4
2 4 5
2 3 3
4 5 1