시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 37 17 16 44.444%

문제

병찬이가 운영하는 “Pineapple Pizza is A Pizza”, 줄여서 “PPAP” 회사는 매우 맛있는 파인애플 피자를 만든다. 하지만 PPAP 회사의 파인애플 피자에 의문을 품은 라이벌 회사가 PPAP 회사를 고발하였다! 회사를 지키기 위하여, 병찬이는 최대한 품질 좋은 파인애플 피자를 만들어야 한다.

파인애플 피자는 얼마나 맛있는 파인애플과 도우를 쓰느냐에 따라 결정된다. 파인애플의 품질이 C, 도우의 품질이 D라면, 그 피자는 C XOR D 의 맛을 가진다. 병찬이는 총 개의 파인애플과 도우를 가지고 있고, 이를 이용하여 개의 파인애플 피자를 만들어야 한다. 항상 최고급의 파인애플 피자를 만든다는 것을 증명하기 위하여, 병찬이는 개의 특별한 파인애플 피자의 맛의 최소값을 최대화하고자 한다.

입력

첫 줄에 (1 ≤ N ≤ 100)이 주어진다.

두 번째 줄에 정수 C1, C2, ... , C(1 ≤ Ci ≤ 109)이 주어진다. 세 번째 줄에 정수 D1, D2, ... , D(1 ≤ Di ≤ 109)이 주어진다.

출력

개의 파인애플 피자의 맛의 최소값의 최대값을 구하여라.

예제 입력 1

5
1 2 3 4 5
5 4 3 2 1

예제 출력 1

3

힌트

파인애플과 도우의 조합을 (1,2), (2,5), (3,4), (4,3), (5,1)로 할 경우, 1 XOR 2 = 3, 2 XOR 5 = 7, 3 XOR 4 = 7, 4 XOR 3 = 7, 5 XOR 1 = 4로 최소값이 3이 나온다. 이 이외에도 최소값이 3이 되게하는 조합이 존재하나, 최소값이 4 이상이 나오게 하는 조합은 없다.

출처

University > POSTECH > 2019 PPC E번