Problem:
 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 \mbox{ XOR } ?  The XOR of integers A and B , A \mbox{ XOR } B , is defined as follows:  When A \mbox{ 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 \mbox{ XOR } 5 = 6 . (In base two: 011 \mbox{ 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.

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a = a + a[:-1]

da = [a[i] ^ a[i+1] for i in range(len(a) - 1)]
db = [b[i] ^ b[i+1] for i in range(len(b) - 1)]


fail = [0 for i in range(len(da))]
fail[0] = -1
p = 0
for q in range(2, len(da)):
    while p >= 0 and da[q-1] != da[p]:
        p = fail[p]
    p += 1
    fail[q] = p

p = 0
q = 0
while p + q < len(da):
    if db[q] == da[p+q]:
        if q == len(db) - 1:
            print(p, a[p] ^ b[0])
            p += q - fail[q]
            q = fail[q]
        else:
            q += 1
    else:
        p += q - fail[q]
        if q > 0:
            q = fail[q]

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def Z_algorithm(s):
        n = len(s)
        z = [0]*n
        z[0] = n
        c = 1
        for i in range(1,n):
            if i+z[i-c] < c+z[c]:
                z[i] = z[i-c]
            else:
                j = max(0,c+z[c]-i)
                while i+j < n and s[j] == s[i+j]:
                    j += 1
                z[i] = j
                c = i
        return z
    n = I()
    a = LI()
    b = LI()
    c = [a[i]^a[(i+1)%n] for i in range(n)]
    d = [b[i]^b[(i+1)%n] for i in range(n)]
    z = Z_algorithm(d+c*2)[n:]
    for k in range(n):
        if z[k] >= n:
            print(k,a[k]^b[0])
    return


if __name__ == "__main__":
    solve()

Solution (Python):

maxN = int(6e5 + 100)
a = [0] * maxN
b = [0] * maxN
ans = [0] * maxN

def solve() :
    L = R = 0
    for i in range(2, 3 * n + 1) :
        if i > R :
            L = R = i
            while R + 1 <= 3 * n and (a[i] ^ a[1]) == (a[R + 1] ^ a[R - L + 2]): R += 1

            ans[i] = R - L + 1
        else :
            k = i - L + 1
            if ans[k] < R - i + 1 : ans[i] = ans[k]
            else :
                L = i
                while R + 1 <= 3 * n and (a[i] ^ a[1]) == (a[R + 1] ^ a[R - L + 2]): R += 1
                ans[i] = R - L + 1

n = int(input())
inp = input().split()
for i in range(n + 1, 2 * n + 1) : a[i] = int(inp[i - n - 1])
for i in range(2 * n + 1, 3 * n + 1) : a[i] = a[i - n]
inp = input().split()
for i in range(1, n + 1) : a[i] = int(inp[i - 1])

solve()

for i in range(n + 1, 2 * n + 1):
    if ans[i] >= n:
        print(i - n - 1, (a[i] ^ a[1]))

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def Z_algorithm(s):
        n = len(s)
        z = [0]*n
        z[0] = n
        c = 1
        for i in range(1,n):
            if i+z[i-c] < c+z[c]:
                z[i] = z[i-c]
            else:
                j = max(0,c+z[c]-i)
                while i+j < n and s[j] == s[i+j]:
                    j += 1
                z[i] = j
                c = i
        return z
    n = I()
    a = LI()
    b = LI()
    c = [a[i]^a[(i+1)%n] for i in range(n)]
    d = [b[i]^b[(i+1)%n] for i in range(n)]
    z = Z_algorithm(d+c*2)[n:2*n]
    for k in range(n):
        if z[k] >= n:
            print(k,a[k]^b[0])
    return


if __name__ == "__main__":
    solve()

Solution (Python):
import sys
from itertools import combinations, permutations, product, combinations_with_replacement, accumulate
from heapq import heapify, heappop, heappush, heappushpop
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from math import sqrt, log, floor, ceil, factorial, cos, sin, pi
from fractions import gcd
from operator import mul
from functools import reduce
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
LINF = 2**63-1
NIL = -LINF
MOD = 10**9+7
MGN = 4
def AST(exp: bool, msg: str = ""): assert exp, msg
def TAST(exp: bool, msg = ""):
    if exp is False: print("TAssertionError:", msg)
    while exp is False:
        pass
def II(): return int(input())
def IF(): return float(input())
def IS(): return input().replace('\n', '')
def ILCI(n: int): return [II() for _ in range(n)]
def ILCF(n: int): return [IF() for _ in range(n)]
def ILI(): return list(map(int, input().split()))
def ILLI(n: int): return [[int(j) for j in input().split()] for i in range(n)]
def ILF(): return list(map(float, input().split()))
def ILLF(n: int): return [[float(j) for j in input().split()] for i in range(n)]
def LTOS(lst: list, sep: str = ' '): return sep.join(map(str, lst))
def DEC(lst: list): return list(map(lambda x: x-1, lst))
def INC(lst: list): return list(map(lambda x: x+1, lst))

def z_algo(S: str) -> list:
    N = len(S)
    if N == 0:
        return []
    ln = [0] * N
    ln[0] = N  
    i = 1
    w = 0
    while i < N:
        while i + w < N and S[w] == S[i + w]:
            w += 1
        ln[i] = w  
        if w == 0:
            i += 1
        else:
            j = 1
            while i + j < N and j + ln[j] < w:
                ln[i+j] = ln[j]
                j += 1
            i += j
            w -= j
    return ln

def z_algo_search(S: str, W: str) -> list:
    lens = z_algo(W+S)
    if len(lens) == 0:
        return []
    SL = len(S)
    WL = len(W)
    slens = lens[WL:]
    res = []
    for i in range(SL):
        if slens[i] >= WL:
            res.append(i)
    return res

def xor_next(A: list) -> list:    
    N = len(A)
    res = []
    for i in range(N-1):
        res.append(A[i]^A[i+1])
    
    res.append(A[-1]^A[0])
    return res

def main():
    N = II()
    A = ILI()
    B = ILI()

    C = xor_next(A)
    D = xor_next(B)

    
    pos = z_algo_search(C*2, D)
    pos = list(filter(lambda x: x < N, pos))
    
    ans = []
    for i in pos:
        ans.append((i, A[i] ^ B[0]))

    for e in ans:
        print(e[0], e[1])


if __name__ == '__main__':
    main()

Solution (Python):






import sys
input = sys.stdin.readline

import math
from fractions import gcd
from functools import lru_cache





MOD = 10**9 +7
INF = float('inf')






def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr


def lcm(a, b):
    return a * b // gcd (a, b)





N = inputI()
a = inputIL()
b = inputIL()

difa = [0]*N
difb = [0]*N
for i in range(N-1):
  difa[i] = a[i]^a[i+1]
  difb[i] = b[i]^b[i+1]
difa[N-1] = a[0]^a[N-1]
difb[N-1] = b[0]^b[N-1]

if set(difa) != set(difb):
  exit()

memo = []
for i in range(N):
  j = 0
  while difa[(i+j)%N] == difb[j%N]:
    j += 1
    if j == N:
      print(i,a[i]^b[0])
      memo.append(i)
      break
  if len(memo) == 2:
    break

if len(memo) == 2:
  d = memo[1]-memo[0]
  k = memo[1]+d
  while k < N:
    print(k,a[k]^b[0])
    k += d

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

class KmpSearch:
  def __init__(self, word):
    self.word = word
    self.table = [0] * (len(word) + 1)
    self.table[0] = -1
    i, j = 0, 1
    while j < len(self.word):
      matched = self.word[i] == self.word[j]
      if not matched and i > 0:
        i = self.table[i]
      else:
        if matched:
          i += 1
        j += 1
        self.table[j] = i
  def search(self, text):
    table = self.table
    word = self.word
    i, p = 0, 0
    res = []
    while i < len(text):
      if text[i] == word[p]:
        i += 1
        p += 1
      elif p == 0:
        i += 1
      else:
        p = table[p]
      if p == len(word):
        res.append(i - p)
        p = table[p]
    return res

xa = [0] * N
xb = [0] * N
for i in range(N):
  xa[i] = a[i - 1] ^ a[i]
  xb[i] = b[i - 1] ^ b[i]

kmp = KmpSearch(xa)
res = kmp.search(xb + xb[: -1])
rres = []
for x in res: rres.append(((N - x) % N, a[0] ^ b[x]))
rres.sort(key = lambda x: (x[0], x[1]))
for r in rres: print(*r)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ta = [[0] * N for _ in range(30)]
tb = [[0] * N for _ in range(30)]
mxl = max(max(a), max(b)).bit_length()
for i in range(mxl):
  x = 1 << i
  for j in range(N):
    ta[i][j] = int((a[j] & x) > 0)
    tb[i][j] = int((b[j] & x) > 0)

class KmpSearch:
  def __init__(self, word):
    self.word = word
    self.table = [0] * (len(word) + 1)
    self.table[0] = -1
    i, j = 0, 1
    while j < len(self.word):
      matched = self.word[i] == self.word[j]
      if not matched and i > 0:
        i = self.table[i]
      else:
        if matched:
          i += 1
        j += 1
        self.table[j] = i
  def search(self, text):
    table = self.table
    word = self.word
    i, p = 0, 0
    res = []
    while i < len(text):
      if text[i] == word[p]:
        i += 1
        p += 1
      elif p == 0:
        i += 1
      else:
        p = table[p]
      if p == len(word):
        res.append(i - p)
        p = table[p]
    return res
res = [0] * N
vis = [1 for _ in range(N)]
for i in range(mxl):
  kmp = KmpSearch(ta[i])
  s = [0] * (2 * N - 1)
  for j in range(2 * N - 1): s[j] = tb[i][j % N] ^ 1
  xs = set(kmp.search(s))
  tvis = [0] * N
  for j in range(N):
    tvis[j] |= (j in xs)
    res[j] += (j in xs) << i
  xs = set(kmp.search(tb[i] + tb[i][: -1]))
  for j in range(N):
    tvis[j] |= (j in xs)
  for j in range(N):
    vis[j] &= tvis[j]

rres = []
for i in range(N):
  if vis[i]: rres.append(((N - i) % N, res[i]))
rres.sort(key = lambda x: (x[0], x[1]))
for r in rres: print(*r)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))


C = [0] * (2 * N - 1)
D = [0] * N
for i in range(2 * N - 1):
    C[i] = A[i % N] ^ A[(i + 1) % N]
    D[i % N] = B[i % N] ^ B[(i + 1) % N]

class KMP:

    def __init__(self, W):
        self.W = W
        self.L = len(W)
        self.T = self._build(W)

    def _build(self, W):
        T = [0] * self.L
        T[0] = -1
        T[1] = 0
        i = 2
        j = 0

        while i < self.L:
            if W[i - 1] == W[j]:
                T[i] = j + 1
                i += 1
                j += 1
            elif j > 0:
                j = T[j]
            else:
                T[i] = 0
                i += 1

        return T

    def search(self, S):
        m = 0
        i = 0
        L = len(S)
        while m + i < L:
            
            if self.W[i] == S[m + i]:
                i += 1
                if i == self.L:
                    i -= 1
                    ret = m
                    m = m + i - self.T[i]
                    i = self.T[i]
                    yield ret
            else:
                m = m + i - self.T[i]
                if i > 0:
                    i = self.T[i]













kmp = KMP(D)
for x in kmp.search(C):
    xor = A[x] ^ B[0]
    print(x, xor)

Solution (Python):
from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A = []
B = []
ans = []
for i in range(N):
    A.append(a[i]^a[(i+1)%N])
    B.append(b[i]^b[(i+1)%N])
if A == B == [A[0]]*N:
    for i in range(N): 
        ans.append((i,a[i]^b[0]))
else:
    A += A    
    d = defaultdict(list)
    for i in range(N):
        d[B[i]].append(i)
    i = 0
    ans = []
    while i < N:
        ok = True
        for j in range(N):
            if B[N-j-1] != A[N-j-1+i]:
                if d[A[N-j-1]] == []:
                    i += N
                    ok = False
                    break
                else:
                    i += N - d[A[N-j-1+i]][-1] - 1
                    ok = False
                    break
        if ok:
            ans.append((i,a[i]^b[0]))
            if len(d[A[N-1+i]]) == 1:
                i += N
            else:
                i += N - d[A[N-1+i]][-2] - 1
for x in ans:
    print(*x)

Solution (Python):

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))



AX = [A[i]^A[i-1] for i in range(N)]
AX += AX
BX = [B[i]^B[i-1] for i in range(N)]





m = 0
for i in range(1, N):
    if BX[m] == BX[i]:
        m += 1
    else:
        m = 0


i, j, k = 0, 0, 0
while k < N:
    while True:
        
        if AX[i] == BX[j]:
            if j == N-1:
                print(k, A[k]^B[0])
                i += 1
                j = m
                break
            i += 1
            j += 1
        elif j != 0:
            j -= 1
        else:
            i += 1
            break
    
    k = i-j

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

A.append(A[0])
B.append(B[0])

AX=[]
BX=[]
for i in range(N):
    AX.append(A[i]^A[i+1])
    BX.append(B[i]^B[i+1])

AX+=AX[:-1]



LEN=len(BX)
MP=[-1]*(LEN+1) 
BX+="0" 

NOW=-1 

for i in range(LEN):
    while NOW>=0 and BX[i]!=BX[NOW]: 
        NOW=MP[NOW]
    NOW+=1
    
    if BX[i+1]==BX[NOW]: 
        MP[i+1]=MP[NOW]
    else:
        MP[i+1]=NOW
        
LEN2=len(AX)
AX+="0" 

MP_SEARCH=[0]*(LEN2+1) 
NOW=0
for i in range(LEN2):
    while NOW>=0 and AX[i]!=BX[NOW]:
        NOW=MP[NOW]
    NOW+=1

    if AX[i+1]==BX[NOW]: 
        MP_SEARCH[i+1]=MP_SEARCH[NOW]
    else:
        MP_SEARCH[i+1]=NOW
        
    MP_SEARCH[i]=NOW

    if NOW==LEN: 
        NOW=MP[NOW]
        
for i in range(LEN2):
    if MP_SEARCH[i]==LEN:
        print(i-LEN+1,A[i-LEN+1]^B[0])

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

A.append(A[0])
B.append(B[0])

AX=[]
BX=[]
for i in range(N):
    AX.append(A[i]^A[i+1])
    BX.append(B[i]^B[i+1])

AX+=AX[:-1]




LEN=len(BX)
MP=[-1]*(LEN+1) 
NOW=-1 

for i in range(LEN):
    while NOW>=0 and BX[i]!=BX[NOW]: 
        NOW=MP[NOW]
    NOW+=1
    MP[i+1]=NOW

LEN2=len(AX)

MP_SEARCH=[0]*(LEN2) 
NOW=0
for i in range(LEN2):
    while NOW>=0 and AX[i]!=BX[NOW]:
        NOW=MP[NOW]
    NOW+=1
    MP_SEARCH[i]=NOW

    if NOW==LEN: 
        NOW=MP[NOW]
        
for i in range(LEN2):
    if MP_SEARCH[i]==LEN:
        print(i-LEN+1,A[i-LEN+1]^B[0])

Solution (Python):
def get_next_int():
    return int(input().rstrip("\n"))


def get_next_ints(delim=" "):
    return tuple([int(x) for x in input().rstrip("\n").split(delim)])


def main():
    n = get_next_int()

    a = get_next_ints()
    b = get_next_ints()

    a_offsets = []
    b_offsets = []
    for i in range(n):
        a_offsets.append(str(a[i] ^ a[i - 1]))
        b_offsets.append(str(b[i] ^ b[i - 1]))
    
    
    a_text = " ".join(a_offsets)
    b_text = " ".join(b_offsets)
    target_text = a_text + " " + a_text
    start_pos = 0
    if target_text.find(b_text, start_pos) >= 0:
        fisrt_pos = target_text.find(b_text, start_pos)
        fisrt_pos_diff = target_text[:fisrt_pos].count(" ")
        fisrt_xor_diff = b[0] ^ a[fisrt_pos_diff]
        print(fisrt_pos_diff, fisrt_xor_diff)
        if target_text.find(b_text, fisrt_pos+1) >= 0:
            second_pos = target_text.find(b_text, fisrt_pos+1)
            second_pos_diff = target_text[:second_pos].count(" ")
            if second_pos_diff < len(a):
                second_xor_diff = b[0] ^ a[second_pos_diff]
                print(second_pos_diff, second_xor_diff)
                interval = (second_pos_diff - fisrt_pos_diff)
                remain = (n - second_pos_diff - 1) // (second_pos_diff - fisrt_pos_diff)
                for i in range(remain):
                    print(second_pos_diff + interval * (i + 1), [fisrt_xor_diff,second_xor_diff ][i % 2])

if __name__ == '__main__':
    main()

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7





class KMP:
    def __init__(self, needle):
        """
        https://ja.wikipedia.org/wiki/クヌース–モリス–プラット法
        :param typing.Sequence needle: 何を検索するか
        """
        self._needle = needle
        kmp = [0] * (len(needle) + 2)
        kmp[0] = -1
        kmp[1] = 0
        i = 2
        j = 0
        while i < len(needle):
            if needle[i - 1] == needle[j]:
                kmp[i] = j + 1
                i += 1
                j += 1
            elif j > 0:
                j = kmp[j]
            else:
                kmp[i] = 0
                i += 1
        self._kmp = kmp

    def index_of(self, haystack, m=0, i=0):
        """
        m + (haystack[m:] の何番目に needle があるか)
        見つからなければ -1
        needle[i:] のみ比較する
        :param typing.Sequence haystack: 何から検索するか
        :param int m: The position of the current character in haystack
        :param int i: The position of the current character in needle
        :rtype: int
        """
        while m + i < len(haystack):
            if self._needle[i] == haystack[m + i]:
                i += 1
                if i == len(self._needle):
                    return m
            else:
                m += i - self._kmp[i]
                if i > 0:
                    i = self._kmp[i]
        return -1

    def search(self, haystack):
        """
        ret[i]: haystack[i:i+len(needle)] == needle
        :param typing.Sequence haystack: 何から検索するか
        :rtype: list of bool
        """
        ret = [False] * len(haystack)
        m = 0
        i = 0
        while m + i < len(haystack):
            m = self.index_of(haystack, m=m, i=i)
            if m < 0:
                break
            ret[m] = True
            m += len(self._needle) - self._kmp[len(self._needle) - 1] - 1
            i = max(0, self._kmp[len(self._needle) - 1])
        return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
B = list(map(int, sys.stdin.buffer.readline().split()))


def test():
    ans = []
    
    for k in range(N):
        b = np.roll(B, k)
        x = A[0] ^ b[0]
        a = A ^ x
        if np.all(a == b):
            ans.append((k, x))
    for r in ans:
        print(*r)




xa = []
xb = []
for a1, a2 in zip(A, A[1:] + [A[0]]):
    xa.append(a1 ^ a2)
for b1, b2 in zip(B, B[1:] + [B[0]]):
    xb.append(b1 ^ b2)

kmp = KMP(xb)
k_ok = kmp.search(xa + xa)
for k in range(N):
    if k_ok[k]:
        x = A[k] ^ B[0]
        print(k, x)

Solution (Python):


from itertools import chain

N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
assert len(a) == N and len(b) == N


a_xor = [a[i] ^ a[(i + 1) % N] for i in range(N)]

b_xor = [b[i] ^ b[i + 1] for i in range(N - 1)]



def kmp_search(T, P):
    m = len(P)
    matches = []
    pi = compute_prefix_func(P)
    q = 0  
    for i, t in enumerate(T):
        while q > 0 and P[q] != t:
            q = pi[q]  
        if P[q] == t:
            q += 1     
        if q == m:
            matches.append(i - (m - 1))
            q = pi[q]  
    return matches

def compute_prefix_func(P):
    m = len(P)
    pi = [0] * (m + 1)
    k = 0
    for q in range(1, m):
        while k > 0 and P[k] != P[q]:
            k = pi[k]
        if P[k] == P[q]:
            k += 1
        pi[q + 1] = k
    return pi

    
    

for k in kmp_search(chain(a_xor, a_xor), b_xor):
    if k < N:
        x = b[0] ^ a[k]
        print(k, x)

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

class RollingHash() :
    
    
    def __init__(self, x, base=26, mod=(1<<61)-1) :
        self.hash = [0]
        self.pow = [1]
        self.mod = mod
        
        for xi in x :
            self.hash.append((self.hash[-1] * base + xi) % mod)
            self.pow.append(self.pow[-1] * base % mod)
            
    
    def get(self, l, r) :
        return (self.hash[r] - self.hash[l] * self.pow[r-l]) % self.mod

da = [a[i] ^ a[(i + 1) % N] for i in range(N)] * 2
db = [b[i] ^ b[(i + 1) % N] for i in range(N)] * 2

RHa1 = RollingHash(da, base=1<<30)
RHa2 = RollingHash(da, base=1<<30, mod=(1<<31)-1)
RHb1 = RollingHash(db, base=1<<30)
RHb2 = RollingHash(db, base=1<<30, mod=(1<<31)-1)

hashb1 = RHb1.get(0, N)
hashb2 = RHb2.get(0, N)

for i in range(N) :
  if RHa1.get(i, N + i) == hashb1 and RHa2.get(i, N + i) == hashb2 :
    print(i, a[i] ^ b[0])

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

A.append(A[0])
B.append(B[0])

AX=[]
BX=[]
for i in range(N):
    AX.append(A[i]^A[i+1])
    BX.append(B[i]^B[i+1])

AX+=AX+[AX[0]]



p=1<<30
mod=(1<<62)+1 

A_TABLE=[0] 
B_TABLE=[0] 

for i in range(len(AX)):
    A_TABLE.append((p*A_TABLE[-1]%mod+AX[i])%mod) 

for i in range(len(BX)):
    B_TABLE.append((p*B_TABLE[-1]%mod+BX[i])%mod) 

def hash(i,j): 
    return (A_TABLE[j]-A_TABLE[i]*pow(p,j-i,mod))%mod

BH=B_TABLE[-1]
ANS=[]
for i in range(N):
    if hash(i,i+N)==BH:
        ANS.append((i,A[i]^B[0]))

for a in ANS:
    print(*a)

Solution (Python):
class RollingHash:
    def __init__(self, s: list, base: int = 1007, mod: int = 10**9 + 7):
        self.s = s
        self.n = len(s)
        self.base = base
        self.mod = mod

        
        self.h_cum = [0] * (self.n + 1)  
        self.b_pow = [1] * (self.n + 1)  
        for i in range(self.n):
            self.h_cum[i + 1] = (self.h_cum[i] * base + s[i]) % mod
            self.b_pow[i + 1] = (self.b_pow[i] * base) % mod

    def get_hash(self, l: int, r: int) -> int:
        
        hash_val = self.h_cum[r] - self.h_cum[l] * self.b_pow[r - l] % self.mod
        if hash_val < 0:
            hash_val += self.mod
        return hash_val


n = int(input())
a = tuple(map(int, input().split()))
b = tuple(map(int, input().split()))

a_xor = [a[i % n] ^ a[(i + 1) % n] for i in range(n * 2)]
b_xor = [b[i % n] ^ b[(i + 1) % n] for i in range(n * 2)]

a_xor_rh = RollingHash(a_xor)
b_xor_rh = RollingHash(b_xor)

b_hash = b_xor_rh.get_hash(0, n)
for k in range(n):
    if a_xor_rh.get_hash(k, k + n) == b_hash:
        x = a[k] ^ b[0]
        print(k, x)

Solution (Python):
class RollingHash:
    def __init__(self, s: list, base: int = 1007, mod: int = 10**9 + 7):
        self.s = s
        self.n = len(s)
        self.base = base
        self.mod = mod

        
        self.h_cum = [0] * (self.n + 1)  
        self.b_pow = [1] * (self.n + 1)  
        
        
        
        for i, si in enumerate(s):
            self.h_cum[i + 1] = (self.h_cum[i] * base + si % mod) % mod
            self.b_pow[i + 1] = (self.b_pow[i] * base) % mod

    def get_hash(self, l: int, r: int) -> int:
        
        hash_val = self.h_cum[r] - self.h_cum[l] * self.b_pow[r - l] % self.mod
        if hash_val < 0:
            hash_val += self.mod
        return hash_val

















n = int(input())
a = tuple(map(int, input().split()))
b = tuple(map(int, input().split()))



a_xor = [a[i % n] ^ a[(i + 1) % n] for i in range(n)] * 2
b_xor = [b[i % n] ^ b[(i + 1) % n] for i in range(n)] * 2

a_xor_rh = RollingHash(a_xor)
b_xor_rh = RollingHash(b_xor)

b_hash = b_xor_rh.get_hash(0, n)
for k in range(n):
    if a_xor_rh.get_hash(k, k + n) == b_hash:
        x = a[k] ^ b[0]
        print(k, x)

Solution (Python):
class RollingHash:
    def __init__(self, s: list, base: int = 1007, mod: int = 10**9 + 7):
        self.s = s
        self.n = len(s)
        self.base = base
        self.mod = mod

        
        self.h_cum = [0] * (self.n + 1)  
        self.b_pow = [1] * (self.n + 1)  
        for i in range(self.n):
            self.h_cum[i + 1] = (self.h_cum[i] * base + s[i]) % mod
            self.b_pow[i + 1] = (self.b_pow[i] * base) % mod

    def get_hash(self, l: int, r: int) -> int:
        
        hash_val = self.h_cum[r] - self.h_cum[l] * self.b_pow[r - l] % self.mod
        if hash_val < 0:
            hash_val += self.mod
        return hash_val


class RollingHashMulti:
    def __init__(self,
                 s: list,
                 base_list: list = [1007, 2009],
                 mod_list: list = [10**9 + 7, 10**9 + 9]):
        self.n = len(base_list)
        self.base_list = base_list
        self.mod_list = mod_list
        self.rh_list = [
            RollingHash(s, base_list[i], mod_list[i]) for i in range(self.n)
        ]

    def get_hash(self, l: int, r: int) -> tuple:
        return tuple(self.rh_list[i].get_hash(l, r) for i in range(self.n))


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a_xor = [a[i % n] ^ a[(i + 1) % n] for i in range(n * 2)]
b_xor = [b[i % n] ^ b[(i + 1) % n] for i in range(n * 2)]

a_xor_rh = RollingHashMulti(a_xor)
b_xor_rh = RollingHashMulti(b_xor)

for k in range(n):
    if a_xor_rh.get_hash(k, k + n) == b_xor_rh.get_hash(0, n):
        x = a[k] ^ b[0]
        print(k, x)

Solution (Python):
num = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = []
d = []

for i in range(num):
    c.append(a[i] ^ a[(i+1)%num])
    d.append(b[i] ^ b[(i+1)%num])
    
c += c





table = [0]
k = 0
for i in range(1, num+1):
    table.append(k)
    if i == num:
        continue
    
    if d[i] == d[k]:
        k += 1
    else:
        k = 0



i = 0 
j = 0 
k = 0 
while k < num:
    
    while True:
        
        if c[i] == d[j]:
            if j == num - 1:
                print(k, a[k] ^ b[0])
                i += 1
                j = table[num]
                k = i - j
                break
            
            i += 1
            j += 1
        elif j != 0:
            j -= 1
        else:    
            i += 1
            j = table[j]
            break
    
    k = i - j

Solution (Python):
def xor_next(values):
    result = [0] * len(values)
    for i in range(len(values)):
        result[i] = values[i] ^ values[(i+1) % len(values)]
    return result


def make_mp_table(values):
    result = [-1] * (len(values) + 1)
    j = -1
    for i in range(len(values)):
        while j != -1 and values[j] != values[i]:
            j = result[j]
        j += 1
        result[i+1] = j
    return result


def mp_find(target, pattern, table):
    result = []
    j = 0
    for i in range(len(target)):
        while(j != -1 and pattern[j] != target[i]):
            j = table[j]
        j += 1
        if j == len(pattern):
            result.append(i-(j-1))
            j = table[j]
    return result


def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    xa = xor_next(a)
    xb = xor_next(b)
    mp_t = make_mp_table(xa)
    xb += xb
    res = mp_find(xb, xa, mp_t)
    res.sort(reverse=True)
    for i in range(len(res)):
        k = n-res[i]
        if(k >= n):
            continue
        x = a[k] ^ b[0]
        print(str(k) + ' ' + str(x))


main()