Description

In the class of ChuanZhi training students, to liven up the atmosphere and reinforce knowledge of bitwise operations, the students play a game.

There are $n(n\le10^6)$ students in the class. Each student receives two cards, a red card and a black card. Each card has a non-negative integer not exceeding $10^9$. For student $i$, the number on the red card is $a_i$, and the number on the black card is $b_i$.

Now each student needs to play a number. Each student may either play the number on their red card directly, or play the result of applying bitwise XOR to their red-card number and their black-card number. In the end, the teacher collects all numbers played by the students.

Among these numbers, the one that appears the most times is the mode. Under the optimal cooperative strategy of all students, we want the number of occurrences of the mode to be as large as possible. What is the number that appears the most times?

Input Format

The first line contains a positive integer $n$.

The next $n$ lines follow. On line $i$, two non-negative integers $a_i,b_i$ represent the numbers on the red card and the black card of student $i$.

Output Format

Output one integer, representing the answer. If there are multiple solutions, output the smallest one.

4
21 9
28 9
28 3
17 4

21

Hint

Explanation of the sample:

The maximum number of occurrences of a mode is $3$. There are two ways:

• Student $1$ plays the red card directly, student $2$ plays the XOR of red and black, student $3$ plays either one, and student $4$ plays the XOR of red and black. Then students $1,2,4$ can all play $21$.
• Student $1$ plays the XOR of red and black, student $2$ plays the red card directly, student $3$ plays the red card directly, and student $4$ plays either one. Then students $1,2,3$ can all play $28$.

So both $21$ and $28$ are modes with the maximum number of occurrences, because at most it can occur $3$ times, and there is no plan that makes it occur $4$ times. But since the problem requires that if there are multiple solutions we output the smaller one, we should output $21$.

Translated by ChatGPT 5