Under construction

Still being built. Things may change

Delicious Pineapple Pizza

Interview

Time limit1sMemory limit256 MB

Summary
Pair each pineapple with a dough to make N pizzas, maximizing the smallest XOR value over all pairs.
Level

Medium7 of 10

Topics
Binary search, Bit manipulation, Greedy, Math
Solved
No attempts yet

Problem

Byeongchan runs "Pineapple Pizza is A Pizza", or PPAP for short, a company that makes very delicious pineapple pizza. But a rival company, doubting PPAP's pineapple pizza, has filed a complaint against PPAP! To defend the company, Byeongchan must make pineapple pizzas of the highest possible quality.

How delicious a pineapple pizza is depends on how good the pineapple and the dough are. If the pineapple has quality CC and the dough has quality DD, the pizza has taste C XOR DC \text{ XOR } D. Byeongchan has NN pineapples and doughs in total, and must use them to make NN pineapple pizzas. To prove that he always makes the finest pineapple pizza, Byeongchan wants to maximize the minimum taste among the NN special pineapple pizzas.

Input

The first line gives NN (1 ≤ NN ≤ 100).

The second line gives integers C1,C2,…,CNC_1, C_2, \dots, C_N (1 ≤ CiC_i ≤ 10910^9). The third line gives integers D1,D2,…,DND_1, D_2, \dots, D_N (1 ≤ DiD_i ≤ 10910^9).

Output

Find the maximum possible value of the minimum taste among the NN pineapple pizzas.

Hint

If the pineapple-dough pairs are (1,2), (2,5), (3,4), (4,3), (5,1), then 1 XOR 2 = 3, 2 XOR 5 = 7, 3 XOR 4 = 7, 4 XOR 3 = 7, 5 XOR 1 = 4, so the minimum is 3. Other pairings also give a minimum of 3, but no pairing gives a minimum of 4 or more.

Examples1

  1. Example 1

    Input
    5
    1 2 3 4 5
    5 4 3 2 1
    
    Expected output
    3