34228번 - 턴제 전략 XOR 게임

문제

건우와 준혁이는 정수가 쓰여진 카드를 각각 $N$개씩 가지고 있다.

건우가 가진 카드에 쓰여진 정수는 $A_1, A_2, \ldots, A_N$이고 준혁이가 가진 카드에 쓰여진 정수는 $B_1, B_2, \ldots, B_N$이다. 서로 카드에 쓰여져 있는 정수를 볼 수 있다.

건우와 준혁이는 가진 카드로 XOR 게임을 한다. 각 라운드마다 다음 과정이 진행되며 총 $N-1$번의 라운드를 진행한다. 가장 처음에 $T = 0$이다.

• 건우는 자신이 가진 카드 중 하나를 골라 내려놓는다.
• 준혁이는 건우가 내려놓은 카드를 보고 자신이 가진 카드 중 하나를 골라 내려놓는다.
• 두 사람 모두 한 번 내려놓은 카드는 다시 내려놓을 수 없다.
• 건우가 내려놓은 카드의 수를 $a,ドル 준혁이가 내려놓은 카드의 수를 $b$라고 할 때, $T$를 $T \oplus a \oplus b$로 바꾼다.

이때 두 정수 $x$와 $y$에 대해 $x \oplus y$ 연산은 두 수의 XOR(exclusive OR)로 정의된다.

건우는 $N-1$번의 라운드 이후 $T$를 최대화하려고 하고, 준혁이는 최소화하려고 한다. 두 사람이 게임을 최선으로 진행하였을 때 $N-1$번의 라운드 종료 이후 $T$를 구하여라.

입력

첫째 줄에 $N$이 주어진다. $(1 \le N \le 300,000円)$

둘째 줄에 $A_1, A_2, \ldots, A_N$가 공백으로 구분되어 주어진다. $(0 \le A_i \le 10^9)$

셋째 줄에 $B_1, B_2, \ldots, B_N$가 공백으로 구분되어 주어진다. $(0 \le B_i \le 10^9)$

출력

첫째 줄에 두 사람이 게임을 최선으로 진행하였을 때 $N-1$번의 라운드 종료 이후 $T$를 출력한다.

제한

노트

두 수의 XOR 연산은, 두 수를 이진수로 나타냈을 때 각 비트 자리에서 서로 다르면 1ドル,ドル 같으면 0ドル$이 되는 비트 연산이다. 예를 들어, 6ドル$과 4ドル$를 이진수로 나타내면 각각 110ドル_{(2)},ドル 100ドル_{(2)}$이 되고, 두 수를 XOR한 값은 010ドル_{(2)}$으로 2ドル$가 된다.