007 - XOR Operations Puzzle

問題文

　長さ $N$ の非負整数列 $A = (A_1, A_2, \dots, A_N)$ と $B = (B_1, B_2, \dots, B_N)$ が与えられます。あなたは、数列 $A$ に対して以下の操作を 好きな回数（0回でもよい）行うことができます。

• $2 \le i \le N-1$ を満たす整数 $i$ を1つ選び、$A_i$ を $A_{i-1} \oplus A_{i+1} \oplus A_i$ に置き換える。

　ここで、$\oplus$ はビットごとの排他的論理和を表します。 数列 $A$ を数列 $B$ に完全に一致させることができるか判定し、可能な場合は必要な最小の操作回数を、不可能な場合は -1 を出力してください。

制約

• $3 \le N \le 2 \times 10^5$
• $0 \le A_i, B_i < 2^{30}$
• 入力はすべて整数である

入出力

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N

出力

数列 $A$ を数列 $B$ に一致させることができる場合は必要な最小の操作回数を、そうでない場合は -1 を出力せよ。

サンプル

入力例 1

4
1 2 3 4
1 0 3 4

出力例 1

1

入力例 2

4
0 3 1 0
0 1 3 0

出力例 2

3

入力例 3

3
1 2 3
1 2 4

出力例 3

-1

提出

提出はこちらから行えます。