Submit solution

Points: 15 (partial)
Time limit: 10.0s
Memory limit: 256M

Problem type

Ruby "200cm" Sun has a problem: she cannot reach the freezer section of her fridge! To assist her with the vertical challenge, she installed a retractable stepladder on the side of the fridge to help her reach the top.

Additionally, to improve at her chances of making CCO this year, she configured the stepladder to give her a programming challenge she needs to complete every time she wants to use it. However, yesterday she got a problem she didn't know how to solve. Can you help her solve it?

The problem is as follows:

There is a sequence of N numbers a_1, a_2, \ldots, a_N. For a constant value c, define b_1, b_2, \ldots, b_N as a sequence such that b_i=a_i\oplus c. Can you select a constant c such that the MEX of b_1, b_2, \ldots, b_N is maximized?

Note: the MEX of a sequence of non-negative integers b_1, b_2, \ldots b_N is defined as the smallest integer X such that X \ge 0 and b_i \neq X for all 1 \le i \le N.


For all subtasks:

T \in \{1, 30\} (T is the number of test cases)

1 \le N \le 2 \times 10^5

0 \le a_i \le 10^9

Subtask 1 [10%]

1 \le N \le 200

0 \le a_i \le 200

Subtask 2 [10%]

1 \le N \le 200

Subtask 3 [20%]

1 \le N \le 2\,000

Subtask 4 [60%]

No additional constraints.

Input Specification

The first line of input contains T, the number of test cases. Next, T test cases follow.

The first line of each test case contains the integer N.

The second line of each test case contains the integers a_1, a_2, \ldots, a_N.

Output Specification

For each test case, output two space separated integers: the maximum possible MEX of b_1, b_2, \ldots, b_N and the value of c that maximizes that MEX. If multiple values of c exist, output the smallest one.

The output of each test case should be on its own line.

Sample Input

11 4 5 23 10

Sample Output

2 4


If we choose c=4, then we get the sequence 15,0,1,19,14 which has a MEX of 2 (and it can be shown that the MEX will never be greater than 2). While there are other values of c that give us a MEX of 2, 4 is the smallest one of them.


There are no comments at the moment.