能量分流

题目描述

夜之城的荒坂网络中存储着 $n$ 个量子能量节点，每个节点拥有能量值 $a_i$。作为一名潜入荒坂主机的网潜者，你的目标是将所有节点的能量完全清零，从而关闭该区域的防火墙。

你可以反复执行一种名为 “能量分流（Energy Split）” 的黑客操作。

首先，你可以选择一个长度为 $n$ 的能量调制数组 $b$，使其满足以下两个条件：

1. 对于每个节点 $(1 \le i \le n)$，能量调制值满足 $0 \le b_i \le a_i$

2. 对于这个数组 $b$，必须存在某个切割点 $(1 \le i < n)$，使得

   $$b_1 + \dots + b_i = b_{i+1} + \dots + b_n$$

执行一次操作后，你会把每个节点能量降为: $a_i = a_i - b_i$.

你的任务是： 在不触发防火墙的前提下（满足条件 1 与条件 2），以最少的操作次数将所有能量节点完全清零。

若任何方式都无法成功清零所有节点，则输出 -1。 题目保证在给定的约束下，最优答案的操作次数不超过 40 次。

输入格式

第一行：测试用例数量 $t(1 \le t \le 10^4)$。

每组测试用例包含：

• 第一行一个整数 $n (2 \le n \le 5 \times 10^4)$，表示量子能量节点数量。
• 第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n (1 \le a_i \le 10^{12})$ 表示各节点初始能量。

保证所有测试的 $n$ 之和不超过 $5 \times 10^4$。

输出格式

若无解，输出 -1。

若有解：

• 第一行输出一个整数 s$(1 \le s \le 40)$——所需最少的能量分流次数；
• 接着输出 s 行，每行输出 n 个整数 $b_1, b_2, \dots, b_n$，表示本次操作从每个节点抽取的能量。

如果有多组解，输出任意一组即可。 所有操作执行后必须满足所有能量节点均为 0。

样例 1

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

1
1 2 3
-1
2
3 1 1 1
2 2 0 4

提示

第一组中直接取 $b = a$ 即可，因 $1 + 2 = 3$；

第二组无法清零；

第三组示例给出了可行方案：

• 第一次操作：取 $b = [3, 1, 1, 1]$，分割点为 $1$，使得 $3 = 1+1+1$，能量变为 $a = [2, 2, 0, 4]$
• 第二次操作：取 $b = [2, 2, 0, 4]$，分割点为 $2$，使得 $2+2 = 0 + 4$，能量变为 $a = [0, 0, 0, 0]$