Yet Another XOR Problem

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

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

  • XOR all the elements of aa with KK. That is, assign ai=aiKa_i = a_i \oplus K for all 1in1 \le i \le n, where \oplus is the bitwise xor operator.

Your goal is to make the array non-decreasing.

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

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

Input

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

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

The second line of each test case contains nn space-separated integers a1,a2,,an(0ai<231)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 nn over all test cases does not exceed 5×1055 \times 10^5.

Output

For each test case, if it is impossible to find such KK, then output 1-1. Otherwise, print two integers — minimum KK and the number of possible K(0K<231)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 11: Minimum K=2K = 2. Assign,

a1=22=0a_1 = 2 \oplus 2 = 0

a2=12=3a_2 = 1 \oplus 2 = 3

So, a1a2a_1 \le a_2. The array is now sorted.

Total possible solutions 10737418241073741824.


Submit

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.