# Yet Another XOR Problem

CUET CSE Fest 2022 - Inte...
Limits 1s, 512 MB

You are given an integer array $a$ of size $n$. You need to select an integer $K(0\le K < 2^{31})$ and perform the following operation exactly once.

• XOR all the elements of $a$ with $K$. That is, assign $a_i = a_i \oplus K$ for all $1 \le i \le n$, where $\oplus$ is the bitwise xor operator.

Your goal is to make the array non-decreasing.

Output the minimum $K$ and number of possible $K(0 \le K < 2^{31})$ that makes the array non-decreasing.

If it is impossible to find such $K$, output $-1$.

## Input

The first line of the input contains a single integer $t(1 \le t \le 10000)$ — the number of test cases.

The first line of each test case contains an integer $n(1 \le n \le 2\times10^5)$ — the number of elements in the array.

The second line of each test case contains $n$ space-separated integers $a_1,a_2,\ldots,a_n (0 \leq a_i < 2^{31})$ — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \times 10^5$.

## Output

For each test case, if it is impossible to find such $K$, then output $-1$. Otherwise, print two integers — minimum $K$ and the number of possible $K(0 \le K < 2^{31})$.

## Sample

InputOutput
6
2
2 1
2
1 2
1
0
6
6 5 4 3 2 1
4
86 107 101 112
8
113 116 97 101 92 103 107 110

2 1073741824
0 1073741824
0 2147483648
7 268435456
8 268435456
-1


Test case $1$: Minimum $K = 2$. Assign,

$a_1 = 2 \oplus 2 = 0$

$a_2 = 1 \oplus 2 = 3$

So, $a_1 \le a_2$. The array is now sorted.

Total possible solutions $1073741824$.

Login to submit.

### Statistics

100% Solution Ratio
KnightshadeEarliest, 1M ago
chrootFastest, 0.0s
YouKnowWhoLightest, 5.6 MB
chrootShortest, 965B
Toph uses cookies. By continuing you agree to our Cookie Policy.