给定一个整数 $$$k$$$ 和一个长度为 $$$n$$$ 的数组 $$$a$$$,其中每个元素对于所有 $$$1 \le i \le n$$$ 都满足 $$$0 \le a_i \le k$$$。您可以对阵列执行以下操作:
- 选择两个不同的索引 $$$i$$$ 和 $$$j$$$($$$1 \le i,j \le n$$$ 和 $$$i \neq j$$$),使得 $$$a_i + a_j = k$$$。
- 选择一个满足 $$$-a_j \le x \le a_i$$$ 的整数 $$$x$$$。
- 将 $$$a_i$$$ 减少 $$$x$$$,将 $$$a_j$$$ 增加 $$$x$$$。换句话说,更新 $$$a_i := a_i - x$$$ 和 $$$a_j := a_j + x$$$。
请注意,对 $$$x$$$ 的约束确保数组 $$$a$$$ 的所有元素在整个操作过程中保持在 $$$0$$$ 和 $$$k$$$ 之间。
你的任务是确定是否可以使用上述操作使数组$$$a$$$非递减$$$^{\text{*}}$$$。如果可能,找到一系列最多 $$$3n$$$ 操作,将数组转换为非递减数组。
可以证明,如果通过上述操作可以使数组不减,则存在最多使用$$$3n$$$操作的解决方案。
$$$^{\text{*}}$$$ 如果对于所有 $$$1 \le i \le n - 1$$$,数组 $$$a_1, a_2, \ldots, a_n$$$ 被认为是非递减的,则它保持 $$$a_i \le a_{i+1}$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数,$$$n$$$ 和 $$$k$$$ ($$$4 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$) - 数组 $$$a$$$ 的长度以及操作所需的总和。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le k$$$) — 数组 $$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果无法使用该操作使数组不减,则输出 $$$-1$$$。
否则,输出操作数 $$$m$$$ ($$$0 \le m \le 3n$$$)。在接下来的 $$$m$$$ 行中,输出三个整数 $$$i$$$、$$$j$$$ 和 $$$x$$$,表示 $$$a_i$$$ 减少 $$$x$$$ 且 $$$a_j$$$ 增加 $$$x$$$ 的操作。
请注意,您是 不 需要尽量减少操作次数。如果有多个解最多需要 $$$3n$$$ 操作,则可以输出任何一个。
示例
输入复制
45 1001 2 3 4 55 61 2 3 5 45 77 1 5 3 110 102 5 3 2 7 3 1 8 4 0
输出复制
0 1 4 1 1 -1 6 1 8 2 3 5 2 5 7 3 5 9 3 8 10 5 2 10 4
注意
在第一个测试用例中,数组已经是非递减的,因此我们不需要执行任何操作。
在第二个测试用例中,我们可以执行 $$$i=4$$$、$$$j=1$$$ 和 $$$x=1$$$ 的操作。 $$$a_4$$$ 减少 $$$1$$$ 变为 $$$5 - 1 = 4$$$,而 $$$a_1$$$ 增加 $$$1$$$ 变为 $$$1 + 1 = 2$$$。运算后,数组变成$$$[2, 2, 3, 4, 4]$$$,是非减的。
请注意,还有其他方法可以使数组不递减,只要它们不使用超过 $$$3 \cdot n = 15$$$ 操作,所有这些方法都将被认为是正确的。
在第三个测试用例中,不可能使数组不减。这是因为没有不同的索引对 $$$i$$$ 和 $$$j$$$ 其中 $$$a_i + a_j = 7$$$,因此无法对数组进行任何操作。
在第四个测试用例中,数组变换如下:
- $$$[\textbf{0}, 5, 3, 2, 7, 3, 1, \textbf{10}, 4, 0]$$$
- $$$[0, 5, \textbf{1}, 2, \textbf{9}, 3, 1, 10, 4, 0]$$$
- $$$[0, 5, 1, 2, \textbf{6}, 3, \textbf{4}, 10, 4, 0]$$$
- $$$[0, 5, 1, 2, \textbf{3}, 3, 4, 10, \textbf{7}, 0]$$$
- $$$[0, 5, 1, 2, 3, 3, 4, \textbf{5}, 7, \textbf{5}]$$$
- $$$[0, \textbf{1}, 1, 2, 3, 3, 4, 5, 7, \textbf{9}]$$$