题目描述

给定两个长度为 $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)$，每对占一行。如果没有满足条件的有序对，输出为空。

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\ <\ 2^{30}$