给定一个数组 $$$a$$$,由 $$$n$$$ 正整数组成。您可以进行以下操作:
- 选择大小为 $$$n$$$ 的数组 $$$b$$$,使得以下属性成立:
- $$$0 \leq b_i \leq a_i$$$ 对于每个 $$$1 \leq i \leq n$$$
- 存在索引 $$$1\leq i \lt n$$$ 使得 $$$b_1+b_2+\ldots+b_i=b_{i+1}+b_{i+2}+\ldots+b_n$$$。也就是说,长度为$$$i$$$的前缀之和等于长度为$$$n-i$$$的后缀之和。
- 然后,对于每个 $$$1 \leq i \leq n$$$,从 $$$a_i$$$ 中减去 $$$b_i$$$。
你的任务是将所有元素更改为$$$0$$$。找到 最小值 所需的操作次数。
然后,输出执行操作的方式。如果无论使用多少次操作都无法将 $$$a$$$ 的所有元素更改为 $$$0$$$,请改为打印 $$$-1$$$。可以看出,在该问题的约束下,所需的最少运算次数最多为$$$17$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 5\cdot 10^4$$$) — 数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq 10^{12}$$$) — 表示数组 $$$a$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5\cdot 10^4$$$。
输出
对于每个测试用例,如果没有解决方案,则输出 $$$-1$$$。
否则,首先输出一个整数 $$$s$$$ ($$$1 \leq s \leq 17$$$) – 将 $$$a$$$ 的所有元素更改为 $$$0$$$ 的最少操作数。
然后,在接下来的 $$$s$$$ 行中,每行输出 $$$n$$$ 个整数 $$$b_1,b_2,\ldots,b_n (0 \leq b_i \leq a_i)$$$ — 表示每个操作的数组 $$$b$$$。
执行操作后,$$$a$$$的所有元素都应更改为$$$0$$$。
示例
输入复制
331 2 322 545 3 1 5
输出复制
1 1 2 3 -1 2 3 1 1 1 2 2 0 4
注意
在第一个测试用例中,我们可以简单地在操作中选择 $$$b=a$$$ 。这是有效的,因为 $$$b_1+b_2=b_3$$$。
在第二个测试用例中,可以证明不可能将$$$a$$$的所有元素更改为$$$0$$$。