题目描述

非負整数からなる長さ $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$ )。

输入格式

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

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

输出格式

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

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

题目大意

题目描述

给定两个长度为 $n$ 的序列 $a=\{a_0,a_1,\cdots,a_{n-1}\}$ 和 $b=\{b_0,b_1,\cdots,b_{n-1}\}$，输出所有有序数对 $(k,x)$ ，满足：

1. $0\leq k<n$ 且 $x\geq 0$。
2. 序列 $a'=b$，其中 $a'_i = a_{i+k\bmod n}\operatorname{xor} x\ (0\leq i<n)$，“$\operatorname{xor}$”表示按位异或。

输入格式

第一行一个整数 $n$。
第二行 $n$ 个整数，依次是 $a_0,a_1,\cdots,a_{n-1}$。
第三行 $n$ 个整数，依次是 $b_0,b_1,\cdots,b_{n-1}$。

输出格式

输出所有满足条件有序对 $(k,x)$，每对占一行。如果没有满足条件的有序对，输出为空。

数据范围

$1\leq n\leq 2\times 10^5$，$0\leq a_i,b_i<2^{30}$。

3
0 2 1
1 2 3

1 3

5
0 0 0 0 0
2 2 2 2 2

0 2
1 2
2 2
3 2
4 2

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

2 2
5 5

2
1 2
0 0

提示

制約

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

Sample Explanation 1

$(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$ と等しくなります。

Sample Explanation 4

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