MAX AND
Basic programming
Bit manipulation
Basics of bit manipulation
59.0% success
2,842 attempts
1s time
256MB memory
1024KB max code

You are given array \(A\), \(B\) each containing \(N\) inetegers. You have to create array \(C\) of \(N\) inetegers where \(C_i = A_i \mathbin{\&} B_i\) (Here, \(\mathbin{\&}\) denotes the Bitwise AND operation). You can shuffle elements of \(A\), \(B\) however you want. Find maximum value of \(C_1 \mathbin{\&} C_2 \mathbin{\&} \dots \mathbin{\&} C _N\).

Input format

  • The first line contains \(T\) denoting the number of test cases. The description of \(T\) test cases is as follows:
  • For each test case:
    • The first line contains an integer \(N\) denotes size of array \(A\), \(B\).
    • The next line contains \(N\) space-separated integers \(A_1, A_2, \dots, A_N\) - denoting the elements of \(A\).

    • The next line contains \(N\) space-separated integers \(B_1, B_2, \dots, B_N\) - denoting the elements of \(B\).

Output format

For each test case, print maximum value of \(C_1 \mathbin{\&} C_2 \mathbin{\&} \dots \mathbin{\&} C _N\) in a separate line.

Constraints

\(1 \leq T \leq 10^5\)
\(1 \leq N \leq 10^5\)
\(0\leq A_i, B_i \leq 10^9\)

The sum of \(N\) over all test cases does not exceed \(10^5\).

Examples
Input
1
2
3 2
2 3
Output
2
Explanation

The best configuration here will be have \(A_1 = 3\), and \(B_1 = 3\), and \(A_2 = 2\) and \(B_2 = 2\). So the array \(C\) will be \([3, 2]\). So the answer will be \(2\) (\(3 \mathbin{\&} 2 = 2\)).

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading Editor...