CF1901C.Add, Divide and Floor

You are given an integer array $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$). In one operation, you can choose an integer $x$ ($0 \le x \le 10^{18}$) and replace $a_i$ with $\lfloor \frac{a_i + x}{2} \rfloor$ ($\lfloor y \rfloor$ denotes rounding $y$ down to the nearest integer) for all $i$ from $1$ to $n$. Pay attention to the fact that all elements of the array are affected on each operation.

Print the smallest number of operations required to make all elements of the array equal.

If the number of operations is less than or equal to $n$, then print the chosen $x$ for each operation. If there are multiple answers, print any of them.

给你一个整数数组 $a_1, a_2, \dots, a_n$（其中 $0 \le a_i \le 10^9$）。在一次操作中，你可以选择一个整数 $x$（其中 $0 \le x \le 10^{18}$），并将所有 $i$（从 $1$ 到 $n$）对应的 $a_i$ 替换为 $\lfloor \frac{a_i + x}{2} \rfloor$（$\lfloor y \rfloor$ 表示将 $y$ 向下取整至最近的整数）。注意：每次操作都会影响数组中的所有元素。

请输出使数组所有元素相等所需的最少操作次数。

如果操作次数不超过 $n$，则还需按顺序输出每次操作所选的 $x$ 值。若存在多种可行方案，输出任意一种即可。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$).

The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

For each testcase, print the smallest number of operations required to make all elements of the array equal.

If the number of operations is less than or equal to $n$, then print the chosen $x$ for each operation in the next line. If there are multiple answers, print any of them.

对于每个测试用例，输出使数组所有元素相等所需的最少操作次数。

如果操作次数小于或等于 $n$，则在下一行输出每次操作所选的 $x$。若存在多个答案，输出任意一个即可。

In the first testcase, all elements are already equal, so $0$ operations are required. It doesn't matter if you print an empty line afterwards or not.

In the second testcase, you can't make less than $2$ operations. There are multiple answers, let's consider the answer sequence $[2, 5]$. After applying an operation with $x = 2$, the array becomes $[\lfloor \frac{4 + 2}{2} \rfloor, \lfloor \frac{6 + 2}{2} \rfloor] = [3, 4]$. After applying an operation with $x = 5$ after that, the array becomes $[\lfloor \frac{3 + 5}{2} \rfloor, \lfloor \frac{4 + 5}{2} \rfloor] = [4, 4]$. Both elements are the same, so we are done.

In the last testcase, you can't make less than $6$ operations. Since $6$ is greater than $n$, you don't have to print them. One possible answer sequence is $[0, 0, 0, 0, 0, 0]$. We are just dividing the second element by $2$ every time and not changing the first element.

在第一个测试用例中，所有元素已经相等，因此需要 $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$（向下取整），而第一个元素保持不变。