分数: 600 点
问题陈述
给出两个序列 a=\{a_0,\ldots,a_{N-1}\} 和 b=\{b_0,\ldots,b_{N-1}\} of N 每个非负整数。
Snuke 将选择一个整数 k 这样 0 \leq k < N 和一个整数 x 不小于 0,创建一个新的长度序列 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,定义如下:
- 当 A \text{ XOR } B 以基数 2 书写,即 2^k的地点 (k \geq 0)是 1 如果 A or B,但不是两者都有 1 在 2^k的地点,以及 0 否则。
约束
- 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}
输出
打印所有对 (k, x) 这样 a' 和 b 将相等,每对使用一行,按升序排列 k (升序 x 对于具有相同的配对 k).
如果没有这样的对,则输出应为空。
示例输入 1
3 0 2 1 1 2 3
示例输出 1
1 3
If (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
没有对可以满足该条件。