問題文

非負整数からなる長さ $N$ の数列 $a=\\{a_0,\\ldots,a_{N-1}\\}$ と $b=\\{b_0,\\ldots,b_{N-1}\\}$ が与えられます。

すぬけ君は $0 \\leq k < N$ を満たす整数 $k$ と、$0$ 以上の整数 $x$ を決めて、新しく長さ $N$ の数列 $a'=\\{a_0',\\ldots,a_{N-1}'\\}$ を次のようにして作ります。

• $a_i'= a_{i+k \\mod N}\\ XOR \\ x$

$a'$ が $b$ と等しくなるような $(k,x)$ の組を全て求めてください。

$\\text{ XOR }$ とは

整数 $A, B$ のビットごとの排他的論理和 $a \\text{ XOR } b$ は、以下のように定義されます。

• $A \\text{ XOR } B$ を二進表記した際の $2^k$ ($k \\geq 0$) の位の数は、$A, B$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $1$、そうでなければ $0$ である。

例えば、$3 \\text{ XOR } 5 = 6$ となります (二進表記すると: $011 \\text{ XOR } 101 = 110$ )。

制約

• $1 \\leq N \\leq 2 \\times 10^5$
• $0 \\leq a_i,b_i < 2^{30}$
• 入力中のすべての値は整数である。

---

入力

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

$N$ $a_0$ $a_1$ $...$ $a_{N-1}$ $b_0$ $b_1$ $...$ $b_{N-1}$

出力

$a'$ と $b$ が等しくなるような $(k,x)$ の組を、$1$ 行に $1$ 組ずつ、$k$ の昇順 ($k$ が等しいものは $x$ の昇順) にすべて出力せよ。

このような組が存在しない場合の出力は空でよい。

---

入力例 1

3
0 2 1
1 2 3

出力例 1

1 3

$(k,x)=(1,3)$ のとき、

• $a_0'=(a_1\\ XOR \\ 3)=1$

• $a_1'=(a_2\\ XOR \\ 3)=2$

• $a_2'=(a_0\\ XOR \\ 3)=3$

となり、$a'$ は $b$ と等しくなります。

---

入力例 2

5
0 0 0 0 0
2 2 2 2 2

出力例 2

0 2
1 2
2 2
3 2
4 2

---

入力例 3

6
0 1 3 7 6 4
1 5 4 6 2 3

出力例 3

2 2
5 5

---

入力例 4

2
1 2
0 0

出力例 4

条件を満たすような組が存在しないこともあります。