给定一个整数数组 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$)。在一次操作中,您可以选择一个整数 $$$x$$$ ($$$0 \le x \le 10^{18}$$$) 并将 $$$a_i$$$ 替换为 $$$\lfloor \frac{a_i + x}{2} \rfloor$$$ ($$$\lfloor y \rfloor$$$ 表示将 $$$y$$$ 向下舍入到最接近的整数) $$$i$$$ 从 $$$1$$$ 到 $$$n$$$。请注意,每次操作都会影响数组的所有元素。
打印使数组的所有元素相等所需的最少操作数。
如果操作数小于或等于 $$$n$$$,则为每个操作打印所选的 $$$x$$$。如果有多个答案,请打印其中任何一个。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$)。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印使数组的所有元素相等所需的最少操作数。
如果操作数小于或等于 $$$n$$$,则在下一行中为每个操作打印所选的 $$$x$$$。如果有多个答案,请打印其中任何一个。
示例
输入 #1
4 1 10 2 4 6 6 2 1 2 1 2 1 2 0 32
输出 #1
0 2 2 5 1 1 6
注意
在第一个测试用例中,所有元素都已经相等,因此需要 $$$0$$$ 操作。之后是否打印空行并不重要。
在第二个测试用例中,您不能进行少于 $$$2$$$ 的操作。有多个答案,让我们考虑答案序列$$$[2, 5]$$$。应用 $$$x = 2$$$ 运算后,数组变为 $$$[\lfloor \frac{4 + 2}{2} \rfloor, \lfloor \frac{6 + 2}{2} \rfloor] = [3, 4]$$$。之后应用 $$$x = 5$$$ 运算后,数组变为 $$$[\lfloor \frac{3 + 5}{2} \rfloor, \lfloor \frac{4 + 5}{2} \rfloor] = [4, 4]$$$。两个元素是相同的,所以我们就完成了。
在最后一个测试用例中,您不能进行少于 $$$6$$$ 的操作。由于 $$$6$$$ 大于 $$$n$$$,因此您不必打印它们。一种可能的答案序列是 $$$[0, 0, 0, 0, 0, 0]$$$。我们只是每次将第二个元素除以$$$2$$$,而不更改第一个元素。