ChatGPT의 역작

대회가 다가오는데도 문제를 만들지 못한 하이비는 결국 AI의 힘을 빌려 다음과 같은 문제를 만들었다.

정수 $x$와 길이 $N$의 정수 수열 $L$, $R$에 대해 다음과 같은 함수 $f$를 정의해 보자.

f(x, L[1..N], R[1..N]):
    value = x
    for i = 1 to N
        l = L[i]
        r = R[i]
        if l ≤ x ≤ r
           value = value^(((x|l)+(x&r)*(l^r)) mod (2**64))
    return (value >= 0x0123456789ABCDEF)

코드에 적힌 |, &, ^, **, 0x, mod 연산은 아래 힌트를 참고하자.

$L$과 $R$이 주어질 때, $f(x,L,R)$이 False이면서 $f(x+1,L,R)$이 True인 $x$를 찾으면 된다.

하지만 AI가 만들어 준 이 문제가 너무 어려웠던 하이비는 이 문제를 풀지도 못한 채 내야 할 위기에 처하게 되었다. 하이비를 위해 위 문제의 답을 찾아주자.

첫 번째 줄에는 수열의 길이 $N$이 주어진다. ($1 \le N \le 200000$)

두 번째 줄에는 수열 $L_1, L_2, \ldots, L_N$이 공백으로 구분되어 주어진다.

세 번째 줄에는 수열 $R_1, R_2, \ldots, R_N$이 공백으로 구분되어 주어진다. ($1 \le L_i \le R_i \le 10^{18}$)

첫 번째 줄에 문제의 답으로 가능한 $x$의 값을 출력한다. ($0 \le x \le 10^{18}$)

가능한 답이 여러 가지라면 그중 아무거나 하나를 출력한다.

가능한 답이 없다면 $-1$을 출력한다.

• a&b는 두 수 $a$와 $b$의 비트별 AND다. 두 수를 이진수로 바꾼 뒤, 각 비트가 모두 1이면 1을, 아니면 0을 적는 연산이다. 예를 들어 $1100_{(2)}$와 $0110_{(2)}$의 AND는 $0100_{(2)}$이다.
• a|b는 두 수 $a$와 $b$의 비트별 OR다. 각 비트에서 둘 중 하나라도 1이면 1을, 아니면 0을 적는다. 예를 들어 $1100_{(2)}$와 $0110_{(2)}$의 OR은 $1110_{(2)}$이다.
• a^b는 두 수 $a$와 $b$의 비트별 XOR이다. 각 비트가 서로 다르면 1을, 같으면 0을 적는다. 예를 들어 $1100_{(2)}$와 $0110_{(2)}$의 XOR은 $1010_{(2)}$이다.
• a**b는 $a^b$를 뜻한다. 예를 들어 2**64는 $2^{64} = 18446744073709551616$이다.
• a mod b는 $a$를 $b$로 나눈 나머지다. 예를 들어 $7 \bmod 3 = 1$이다.
• 0x는 16진수 표기를 뜻한다. 예를 들어 0x0123456789ABCDEF는 $81985529216486895$이다.