← 返回题目列表

Codeforces · 1416/B

B. 让他们平等

中文机器翻译题面 查看原题

给定一个数组 $$$a$$$,由 $$$n$$$ 正整数组成,编号从 $$$1$$$ 到 $$$n$$$。您可以执行以下操作不超过 $$$3n$$$ 次:

1. 选择三个整数 $$$i$$$、$$$j$$$ 和 $$$x$$$ ($$$1 \le i, j \le n$$$; $$$0 \le x \le 10^9$$$);
2. 赋值 $$$a_i := a_i - x \cdot i$$$, $$$a_j := a_j + x \cdot i$$$。

每次操作后,数组的所有元素都应为非负数。

你能找到一个不超过 $$$3n$$$ 操作的序列,之后数组的所有元素都相等吗?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^4$$$) — 数组中的元素数量。第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — 数组的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^4$$$。

输出

对于每个测试用例,打印答案如下:

- 如果没有合适的操作顺序,则打印$$$-1$$$;
- 否则,打印一个整数 $$$k$$$ ($$$0 \le k \le 3n$$$) — 序列中的操作数。然后打印 $$$k$$$ 行,其中第 $$$m$$$ 行应包含第 $$$m$$$ 操作的三个整数 $$$i$$$、$$$j$$$ 和 $$$x$$$ ($$$1 \le i, j \le n$$$; $$$0 \le x \le 10^9$$$)。

如果有多个合适的操作序列,则打印其中任何一个。请注意,您不必最小化 $$$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