异或平移

题目描述

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

Snuke 选择满足 $0 \leq k \lt 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$ 行,按 $k$ 升序($k$ 相同时按 $x$ 升序)输出。

如果不存在这样的组,则可以不输出任何内容。

样例

3
0 2 1
1 2 3

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$ 相等。

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 \lt 2^{30}$
• 输入中的所有值都是整数。