Xor Shift

AtCoder

IDabc150_f

Time2000ms

Memory256MB

Difficulty—

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}$ [samples]

Samples

Input #1

3
0 2 1
1 2 3

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

Input #2

5
0 0 0 0 0
2 2 2 2 2

Output #2

Input #3

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

Output #3

2 2
5 5

Input #4

2
1 2
0 0

Output #4

No pairs may satisfy the condition.

API Response (JSON)

{
  "problem": {
    "name": "Xor Shift",
    "description": {
      "content": "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 t",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc150_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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.\nSnuke will choose an integer $k$ such that $0 \\leq k < N$ and an integer $x$ not less t...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments