题目描述

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

Snuke 将选择一个整数 $k$，使得 $0 \\leq k < N$，以及一个不小于 $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$ 的 $\\text{ XOR }$ 运算结果 $A \\text{ XOR } B$ 的定义如下：

• 当将 $A \\text{ XOR } B$ 用二进制表示时，第 $2^k$ 位（$k \\geq 0$）上的数字为 $1$ 当且仅当 $A$ 和 $B$ 中有且只有一个在第 $2^k$ 位上为 $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)$，按照 $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

没有满足条件的序列对。