题目描述

Given are two sequences $a=\{a_0,\ldots,a_{N-1}\}$ and $b=\{b_0,\ldots,b_{N-1}\}$ of $N$ non-negative integers each.

Snuke will choose an integer $k$ such that $0 \leq k \lt N$ and an integer $x$ not less than $0$, to make a new sequence of length $N$, $a'=\{a_0',\ldots,a_{N-1}'\}$, as follows:

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

Find all pairs $(k,x)$ such that $a'$ will be equal to $b$.

What is $\text{ XOR }$?

The XOR of integers $A$ and $B$, $A \text{ XOR } B$, is defined as follows:

• When $A \text{ XOR } B$ is written in base two, the digit in the $2^k$'s place ($k \geq 0$) is $1$ if either $A$ or $B$, but not both, has $1$ in the $2^k$'s place, and $0$ otherwise.

For example, $3 \text{ XOR } 5 = 6$. (In base two: $011 \text{ XOR } 101 = 110$.)

给定两个序列 $a=\{a_0,\ldots,a_{N-1}\}$ 和 $b=\{b_0,\ldots,b_{N-1}\}$ 各为 $N$ 个非负整数

斯努克将选择一个整数 $k$ 使 $0 \leq k \lt N$ 和一个不小于 $0$ 的整数 $x$ 组成一个长度为 $N$ , $a'=\{a_0',\ldots,a_{N-1}'\}$ 的新序列，如下所示：

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

找出所有 $(k,x)$ 对，使得 $a'$ 等于 $b$ 。

$\text{ XOR }$ 是多少？?

整数 $A$ 和 $B$ , $A \text{ XOR } B$ 的 XOR 定义如下：

• 当以二进制写入 $A \text{ XOR } B$ 时，如果 $A$ 或 $B$ （而不是两者）的 $2^k$ 的 $2^k$ 位上有 $1$ ，那么 $2^k$ 位上的数字（ $k \geq 0$ ）就是 $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}$

输出格式

按 $k$ 升序打印所有 $(k, x)$ 和 $a'$ 相等的线对 $b$ ，每对打印一行（ $k$ 相同的线对按 $x$ 升序打印）。

如果没有相同的数据对，则输出结果为空。

样例 #1

样例输入 #1

3
0 2 1
1 2 3

样例输出 #1

1 3

样例 #2

样例输入 #2

5
0 0 0 0 0
2 2 2 2 2

样例输出 #2

0 2
1 2
2 2
3 2
4 2

样例 #3

样例输入 #3

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

样例输出 #3

2 2
5 5

样例 #4

样例输入 #4

2
1 2
0 0

样例输出 #4

说明

数据规模与约定

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq a_i,b_i \lt 2^{30}$
• 所有输入值均为整数。

样例 $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$ 。

样例 $4$ 解释

没有任何一对符合条件。