给定一个循环数组 $$$a$$$,其中包含 $$$n$$$ 个元素,其中 $$$n$$$ 为奇数。在每个操作中,您可以执行以下操作:
- 选择索引 $$$1 \le i \le n$$$ 并将 $$$a_{i - 1}$$$ 增加 $$$1$$$,将 $$$a_i$$$ 增加 $$$2$$$,将 $$$a_{i + 1}$$$ 增加 $$$1$$$。第一个元素之前的元素是最后一个元素,因为这是一个循环数组。
如果循环数组的所有元素都彼此相等,则该循环数组称为平衡数组。
找到任何操作序列可以使这个循环数组平衡或确定这是不可能的。请注意,您不必最小化操作次数。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n < 2 \cdot 10^5$$$,$$$n$$$ 为奇数)——数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{6}$$$) — 数组 $$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例:
- 如果不可能使循环数组平衡,则输出$$$-1$$$。
- 否则,输出 $$$n$$$ 整数 $$$v_1, v_2, \ldots, v_n$$$ ($$$0 \leq v_i \leq 10^{18}$$$) — 其中 $$$v_i$$$ 表示应用于索引 $$$i$$$ 的操作数。可以证明,如果存在解,则在给定的约束条件下也存在解。如果给定约束下有多个解,则输出其中任意一个。
示例
输入 #1
6 3 2 1 2 3 1 2 3 5 1 2 1 2 1 7 1 2 1 2 1 3 1 9 10000 10000 10000 10000 10000 10001 10002 10001 10000 1 10
输出 #1
0 1 0 2 1 0 2 0 3 0 2 4 2 7 0 8 0 6 1 1 1 1 1 1 0 1 1 0
注意
在第一个测试用例中:
- 对索引 $$$i = 2$$$ 执行 $$$1$$$ 操作后,数组 $$$a = [3, 3, 3]$$$。
在第二个测试用例中:
- 对索引 $$$i = 1$$$ 执行 $$$2$$$ 操作后,数组 $$$a = [5, 4, 5]$$$。
- 对索引 $$$i = 2$$$ 执行 $$$1$$$ 操作后,数组 $$$a = [6, 6, 6]$$$。
在第三个测试用例中:
- 对索引 $$$i = 1$$$ 执行 $$$2$$$ 操作后,数组 $$$a = [5, 4, 1, 2, 3]$$$。
- 对索引 $$$i = 3$$$ 执行 $$$3$$$ 操作后,数组 $$$a = [5, 7, 7, 5, 3]$$$。
- 对索引 $$$i = 5$$$ 执行 $$$2$$$ 操作后,数组 $$$a = [7, 7, 7, 7, 7]$$$。