#2723 재재새와 XOR 연산

11  1 s   128 MB  

Description

재재새는 어제 배운 xor(exclusive or) 연산에 대해서 이해를 하고 있는 중이다.

 

1^1 = 0

0^0 = 0

0^1 = 1^0 = 1

2(10) ^ 1(01) = 3(11) 

 

이제 어느정도 이해가 끝난 재재새는 제리에게 알려준다.

"제리 !! 너 xor 알아 ?? 아냐고 !!"

"선배님, 기본인데요.. 설마 저 알려주실.... 저 무시하세요 ??" ... "선배님! 제가 문제 하나 낼게요. 한번 풀어보시죠"

 

제리가 재재새에게 알려준 문제는 다음과 같다.

 

어떤 수 집합 $A, B$가 들어온다. 이 두 집합의 원소의 개수는 $N$개로 동일하다.

또한, 각 원소는 $ 1\leq a_i, b_i \leq 10^{9} $ 를 만족한다.

 

이쯤에서, 새로운 function 에 대해서 설명하겠다.

$func(A, L, R)$ (단, $ 1 \leq L \leq R \leq N $) = 집합 $A$의 구간 $L$부터 $R$까지의 xor 연산 결과이다.

이때, $func(A, L, R) + func(B, L, R)$ 의 값의 최댓 값을 구하면 된다.

Input

$N$ $1 \leq N \leq 1000$

set of A $a_1, a_2, a_3, \dots a_n$

set of B $b_1, b_2, b_3, \dots b_n$

Output

func(A, L, R) + func(B, L, R) 의 값의 최댓 값을 출력하시오.

Sample Input

Sample Output

2
1 2
3 4
10

Source

wowoto9772