Natural Xor - Repovive Premier Round 1 | Repovive

2C. Natural Xor

1500 pts2s256 MB

You are given an array of $n$ positive integers.

In one operation, you choose any two elements $x$ and $y$ from the array, remove both of them, and insert the value $x \oplus y$ (bitwise XOR) into the array.

You will perform exactly $n-1$ operations, so the array becomes a single number.

Determine whether it is possible to choose the operations in such a way that the value $0$ is never produced at any moment, i.e. after every operation the inserted value must be non-zero.

Constraints

$1 \le t \le 100$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$

Input

t \\[0.5em] \left. \begin{array}{l} n \\ a_1 \ a_2 \ \dots \ a_n \end{array} \right\} \times t

Output

For each test case, if it is impossible, print No.

Otherwise, print Yes, and then print $n-1$ lines. The $i$ -th line should contain two integers $x$ and $y$ — the values of the two elements you choose in the $i$ -th operation. Both $x$ and $y$ must be present in the current array, and $x \neq y$ must hold (which guarantees $x \oplus y \neq 0$ ).

After each operation, both $x$ and $y$ are removed from the array, and the value $x \oplus y$ is inserted.

If there are multiple valid answers, you may print any of them.

Samples

Input

Explanation

Case 1

In the first test case, $n = 1$ , so no operations are needed and the answer is Yes.

Case 2

In the second test case, the array is $[1, 3]$ . We choose $x = 3$ and $y = 1$ : since $3 \oplus 1 = 2 \neq 0$ , this is valid. The array becomes $[2]$ .

Case 3

In the third test case, the array is $[7, 7]$ . The only possible operation is to choose both $7$ s, but $7 \oplus 7 = 0$ , which is forbidden. So the answer is No.

Output

Yes
Yes
3 1
No

Input

Explanation

In the first test case, the array is $[3, 5, 3, 7]$ . The total XOR is $3 \oplus 5 \oplus 3 \oplus 7 = 2 \neq 0$ , and the elements are not all equal, so a valid sequence exists.

One valid sequence of operations:

Choose $x = 3$ and $y = 7$ : we get $3 \oplus 7 = 4 \neq 0$ . The array becomes $[5, 3, 4]$ .
Choose $x = 5$ and $y = 4$ : we get $5 \oplus 4 = 1 \neq 0$ . The array becomes $[3, 1]$ .
Choose $x = 3$ and $y = 1$ : we get $3 \oplus 1 = 2 \neq 0$ . The array becomes $[2]$ .

In the second test case, the array is $[1, 2, 3]$ . The total XOR is $1 \oplus 2 \oplus 3 = 0$ . Since XOR is preserved across operations, the final element must be $0$ , which is forbidden. So the answer is No.

Output

Yes
3 7
5 4
3 1
No

You are given an array of $n$ positive integers.

In one operation, you choose any two elements $x$ and $y$ from the array, remove both of them, and insert the value $x \oplus y$ (bitwise XOR) into the array.

You will perform exactly $n-1$ operations, so the array becomes a single number.

Determine whether it is possible to choose the operations in such a way that the value $0$ is never produced at any moment, i.e. after every operation the inserted value must be non-zero.

Constraints

$1 \le t \le 100$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$

t \\[0.5em] \left. \begin{array}{l} n \\ a_1 \ a_2 \ \dots \ a_n \end{array} \right\} \times t

For each test case, if it is impossible, print No.

After each operation, both $x$ and $y$ are removed from the array, and the value $x \oplus y$ is inserted.

If there are multiple valid answers, you may print any of them.

In the first test case, $n = 1$ , so no operations are needed and the answer is Yes.

In the second test case, the array is $[1, 3]$ . We choose $x = 3$ and $y = 1$ : since $3 \oplus 1 = 2 \neq 0$ , this is valid. The array becomes $[2]$ .

In the third test case, the array is $[7, 7]$ . The only possible operation is to choose both $7$ s, but $7 \oplus 7 = 0$ , which is forbidden. So the answer is No.

In the first test case, the array is $[3, 5, 3, 7]$ . The total XOR is $3 \oplus 5 \oplus 3 \oplus 7 = 2 \neq 0$ , and the elements are not all equal, so a valid sequence exists.

One valid sequence of operations:

Choose $x = 3$ and $y = 7$ : we get $3 \oplus 7 = 4 \neq 0$ . The array becomes $[5, 3, 4]$ .
Choose $x = 5$ and $y = 4$ : we get $5 \oplus 4 = 1 \neq 0$ . The array becomes $[3, 1]$ .
Choose $x = 3$ and $y = 1$ : we get $3 \oplus 1 = 2 \neq 0$ . The array becomes $[2]$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

2C. Natural Xor

Input

Output

Samples

2C. Natural Xor

Constraints

Input

Output

Samples

Constraints