310862: CF1901C. Add, Divide and Floor

C. Add, Divide and Floortime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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.

ExampleInput

4
1
10
2
4 6
6
2 1 2 1 2 1
2
0 32

Output

0
2
2 5
1
1
6

Note

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.

题目大意：
给定一个整数数组a[1], a[2], ..., a[n]（0 ≤ a[i] ≤ 10^9），你可以进行以下操作：选择一个整数x（0 ≤ x ≤ 10^18），并将数组中的每个元素a[i]替换为⌊(a[i] + x)/2⌋（⌊y⌋表示对y向下取整）。每次操作会影响数组中的所有元素。求使数组中所有元素相等所需的最小操作次数。如果操作次数小于或等于n，则输出每次操作选择的x值。如果有多个答案，输出其中任意一个。

输入数据格式：
第一行包含一个整数t（1 ≤ t ≤ 10^4）——测试用例的数量。
每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 2 × 10^5）。
第二行包含n个整数a[1], a[2], ..., a[n]（0 ≤ a[i] ≤ 10^9）。
所有测试用例的n之和不超过2 × 10^5。

输出数据格式：
对于每个测试用例，输出使数组中所有元素相等所需的最小操作次数。
如果操作次数小于或等于n，则在下一行中输出每次操作选择的x值。如果有多个答案，输出其中任意一个。题目大意： 给定一个整数数组a[1], a[2], ..., a[n]（0 ≤ a[i] ≤ 10^9），你可以进行以下操作：选择一个整数x（0 ≤ x ≤ 10^18），并将数组中的每个元素a[i]替换为⌊(a[i] + x)/2⌋（⌊y⌋表示对y向下取整）。每次操作会影响数组中的所有元素。求使数组中所有元素相等所需的最小操作次数。如果操作次数小于或等于n，则输出每次操作选择的x值。如果有多个答案，输出其中任意一个。 输入数据格式： 第一行包含一个整数t（1 ≤ t ≤ 10^4）——测试用例的数量。 每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 2 × 10^5）。 第二行包含n个整数a[1], a[2], ..., a[n]（0 ≤ a[i] ≤ 10^9）。 所有测试用例的n之和不超过2 × 10^5。 输出数据格式： 对于每个测试用例，输出使数组中所有元素相等所需的最小操作次数。 如果操作次数小于或等于n，则在下一行中输出每次操作选择的x值。如果有多个答案，输出其中任意一个。