给定一个包含 $$$n$$$ 元素的数组 $$$a$$$。
您可以执行以下操作不超过 $$$n$$$ 次:选择三个索引 $$$x,y,z$$$ $$$(1 \leq x < y < z \leq n)$$$ 并将 $$$a_x$$$ 替换为 $$$a_y - a_z$$$。运算后$$$|a_x|$$$需要小于$$$10^{18}$$$。
您的目标是使结果数组不递减。如果有多个解决方案,则可以输出任何一个。如果无法实现,也应该报告。
输入
每个测试包含多个测试用例。第一行将包含一个整数 $$$t$$$ $$$(1 \leq t \leq 10000)$$$ — 测试用例的数量。然后是 $$$t$$$ 测试用例。
每个测试用例的第一行包含一个整数 $$$n$$$ $$$(3 \leq n \leq 2 \cdot 10^5)$$$ — 数组 $$$a$$$ 的大小。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots ,a_n$$$ $$$(-10^9 \leq a_i \leq 10^9)$$$,$$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果没有解决方案,则在一行中打印 $$$-1$$$。否则,在第一行中,您应该打印一个整数 $$$m$$$ $$$(0 \leq m \leq n)$$$ — 您执行的操作数。
那么接下来的 $$$m$$$ 行中的第 $$$i$$$ 行应包含三个整数 $$$x,y,z$$$ $$$(1 \leq x < y < z \leq n)$$$— 第 $$$i$$$ 操作的描述。
如果有多个解,则可以输出任何一个。请注意,您不必最小化此任务中的操作数量。
示例
输入 #1
3 5 5 -4 2 -1 2 3 4 3 2 3 -3 -2 -1
输出 #1
2 1 2 3 3 4 5 -1 0
注意
在第一个示例中,数组变为
$$$[-6,-4,2,-1,2]$$$ 第一次操作后,
$$$[-6,-4,-3,-1,2]$$$ 第二次操作后。
在第二个示例中,不可能在任何操作序列之后对数组进行排序。
在第三个示例中,数组已经排序,因此我们不需要执行任何操作。