Jamie, being separated from the safari tour group, has been enticed by a scheming hyena to play a game for money. The hyena gives Jamie ~n~ stones, each with a non-negative integer scratched into it with the hyena's claws.

In one operation, Jamie may choose a non-negative integer ~x~ and simultaneously replace all stone values by ~a_i \to |a_i - x|~.

Jamie may perform this operation up to 3 times, and he wants to make all stones show the same number. As soon as all stones show the same number, the game immediately ends; Jamie cannot perform any further operations after that point. For example, if all stones are already equal, Jamie performs ~0~ operations.

If it is possible to make all stones equal, Jamie wants to produce a valid sequence of operations that results in the smallest possible final value.

Thus, for each of the cases given by the hyena:

• output the minimum possible final value,
• output any sequence of pivots (the values of each ~x~),
• or report that it is impossible.

Input

The first line contains a single integer ~t~ (~1 \leq t \leq 10^4~), the number of test cases.

Each test case contains two lines:

• a single integer ~n~ (~1 \leq n \leq 2\times 10^5~), the number of stones given in this case, and
• ~n~ space-separated integers ~a_1,\dots,a_n~ (~0 \leq a_i \leq 10^9~), the value of each stone.

The sum of ~n~ over all test cases does not exceed ~2\times 10^5~.

Output

For each test case, output -1 if it is impossible to make the stones all have the same value before the game ends.

Otherwise, output two integers v k, where ~v~ is the minimum possible final value and ~0 \leq k \leq 3~ is the number of operations used.

On the next line, output the ~k~ pivots in order. If ~k=0~, output a blank line.

Any valid sequence achieving the minimum final value is accepted.

Example

Input 1

3
2
1 3
4
0 2 4 8
2
0 1

Output 1

1 1
2
1 3
1 4 2
-1

Explanation 1

In the first case, choosing ~x=2~ changes the stones to ~1,1~. The game then ends immediately.

In the second case, the pivots ~1,4,2~ change the stones as follows: 0 2 4 8 -> 1 1 3 7 -> 3 3 1 3 -> 1 1 1 1. It is possible to make all stones equal, and the minimum final value is ~1~.

In the third case, the two stones have values ~0~ and ~1~. Their difference remains odd after every operation, so they can never become equal.

Input 2

1
3
67 67 67

Output 2

67 0
⁠

Explanation 2

The stones are already equal, so Jamie performs no operations and the final value is ~67~.

Input 3

1
4
0 4 6 10

Output 3

1 3
2 5 2

Explanation 3

These operations produces the following arrays: 0 4 6 10 -> 2 2 4 8 -> 3 3 1 3 -> 1 1 1 1.

Note that it is possible to produce an array of all twos with just two operations via operations 5 3. It is important to note that we are looking for the operations that produce the minimum final element among all valid sets, not minimising the amount of operations.