O. Bea the maximizer
time limit per test
3 s
memory limit per test
256 MB
input
standard input
output
standard output
Bea likes big things
Everyone know it

Bea has two arrays $$$a$$$ and $$$b$$$, both of $$$n$$$ integers.

A permutation of length $$$n$$$ is an array of length $$$n$$$ where each number between $$$1$$$ and $$$n$$$ appears exactly once.

Your task is to find a permutation $$$p$$$ of length $$$n$$$ which maximizes the following value:

$$$(a_1 + b_{p_1})$$$ $$$\&$$$ $$$(a_2 + b_{p_2})$$$ $$$\&$$$ ... $$$\&$$$ $$$(a_n + b_{p_n})$$$.

$$$\&$$$ is the bitwise AND operator, If you don't know how it works, remember that you can search for it on the internet ;)

As there can be a lot of solutions, Bea also wants to find one that minimizes the maximum distance from the position of a value on the chosen permutation to it's original position in the sorted permutation, in other words, Bea wants to find one that minimizes the following value: $$$\max_{1 \leq i \leq n} (|i - pos_i|)$$$ where $$$pos_i$$$ is position of $$$i$$$ in the chosen permutation and $$$|x|$$$ is the absolute value of $$$x$$$.

Please, help Bea :(

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 100)$$$. The description of the test cases follows.

The first line consists in one integer $$$n$$$ $$$(2 \leq n \leq 1500)$$$ — the size of the arrays.

Then follows $$$n$$$ integers $$$a_{i}$$$ $$$(0 \leq a_{i} \leq 10^{9})$$$ — the values of $$$a$$$.

Finally follows $$$n$$$ integers $$$b_{i}$$$ $$$(0 \leq b_{i} \leq 10^{9})$$$ — the values of $$$b$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1500$$$.

Output

For each testcase, output two integers per line, the maximum possible value chosing the permutation optimally, and the minimum maximum distance from the position of a value on the chosen permutation to it's original position in the sorted permutation, so that the maximum value continues to be obtained.

Example
Input
4
5
5 13 4 10 0
3 0 2 11 15
3
7 1 2
5 8 1
3
1 2 3
5 4 6
2
1000000000 1000000000
1000000000 1000000000
Output
8 1
2 1
7 2
2000000000 0
Note

—

Problem idea: danx

Problem preparation: danx

Ocurrences: Advanced 9