F - Xor Shift Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600

問題文

非負整数からなる長さ N の数列 a=\{a_0,\ldots,a_{N-1}\}b=\{b_0,\ldots,b_{N-1}\} が与えられます。

すぬけ君は 0 \leq k < 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 )。

制約

  • 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) の組を、1 行に 1 組ずつ、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



条件を満たすような組が存在しないこともあります。

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.

What is \text{ XOR }?

The XOR of integers A and B, A \text{ XOR } B, is defined as follows:

  • When A \text{ XOR } B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.
For example, 3 \text{ XOR } 5 = 6. (In base two: 011 \text{ XOR } 101 = 110.)

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.


Sample Input 1

3
0 2 1
1 2 3

Sample Output 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

and we have a' = b.


Sample Input 2

5
0 0 0 0 0
2 2 2 2 2

Sample Output 2

0 2
1 2
2 2
3 2
4 2

Sample Input 3

6
0 1 3 7 6 4
1 5 4 6 2 3

Sample Output 3

2 2
5 5

Sample Input 4

2
1 2
0 0

Sample Output 4



No pairs may satisfy the condition.