{"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 than $0$, to make a new sequence of length $N$, $a'={a_0',\\ldots,a_{N-1}'}$, as follows:\n\n*   $a_i'= a_{i+k \\mod N}\\ XOR \\ x$\n\nFind all pairs $(k,x)$ such that $a'$ will be equal to $b$.\nWhat is $\\text{ XOR }$?The XOR of integers $A$ and $B$, $A \\text{ XOR } B$, is defined as follows:\n\n*   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.\n\nFor example, $3 \\text{ XOR } 5 = 6$. (In base two: $011 \\text{ XOR } 101 = 110$.)\n\n## Constraints\n\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $0 \\leq a_i,b_i < 2^{30}$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$a_0$ $a_1$ $...$ $a_{N-1}$\n$b_0$ $b_1$ $...$ $b_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc150_f","tags":[],"sample_group":[["3\n0 2 1\n1 2 3","1 3\n\nIf $(k,x)=(1,3)$,\n\n*   $a_0'=(a_1\\ XOR \\ 3)=1$\n    \n*   $a_1'=(a_2\\ XOR \\ 3)=2$\n    \n*   $a_2'=(a_0\\ XOR \\ 3)=3$\n    \n\nand we have $a' = b$."],["5\n0 0 0 0 0\n2 2 2 2 2","0 2\n1 2\n2 2\n3 2\n4 2"],["6\n0 1 3 7 6 4\n1 5 4 6 2 3","2 2\n5 5"],["2\n1 2\n0 0","No pairs may satisfy the condition."]],"created_at":"2026-03-03 11:01:14"}}