F - Xor Shift

Score : $600$ points

Problem Statement

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 < 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$.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq a_i,b_i < 2^{30}$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$

$a_0$ $a_1$ $...$ $a_{N-1}$

$b_0$ $b_1$ $...$ $b_{N-1}$

Output

Print all pairs $(k, x)$ such that $a'$ and $b$ will be equal, using one line for each pair, in ascending order of $k$ (ascending order of $x$ for pairs with the same $k$).

If there are no such pairs, the output should be empty.

3
0 2 1
1 2 3

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$

and we have $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

No pairs may satisfy the condition.