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):
def Z(S):
    res = [0]*len(S)
    res[0] = len(S)
    i = 1
    j = 0
    while i < len(S):
        while i+j < len(S) and S[j] == S[i+j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < len(S) and k+res[k] < j:
            res[i+k] = res[k]
            k += 1
        i += k
        j -= k
    return res

N = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
S = [0]*N
T = [0]*N
for i in range(N):
    S[i] = a[i]^a[(i+1)%N]
    T[i] = b[i]^b[(i+1)%N]
s = 0
t = 0
for i in range(N):
    s += S[i]
    t += T[-i-1]
    if s==t:
        break

ans = []
z = Z(S)
for j in range(N):
    if z[j]==N-j:
        ans.append([(j+i+1)%N,a[0]^b[(-j-i-1)%N]])
ans.sort()
if s!=t:
    ans = []
for s in ans:
    print(*s)

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()
    a_xor = [a[i%n]^a[(i+1)%n] for i in range(2*n)]
    b_xor = [b[i%n]^b[(i+1)%n] for i in range(n)]
    b_xor += a_xor
    z = Z_algorithm(b_xor)
    for k in range(n):
        i = n+k
        x = b[0]^a[k]
        if z[i] >= n:
            print(k,x)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
import sys
BASE, MOD1, MOD2 = (1<<30), (1<<61)-1, (1<<31)-1

class RollingHash():
	def __init__(self, s, base, mod):
		self.mod = mod
		self.pw = pw = [1]*(len(s)+1)

		l = len(s)
		self.h = h = [0]*(l+1)

		v = 0
		for i in range(l):
			h[i+1] = v = (v * base + s[i]) % mod
		v = 1
		for i in range(l):
			pw[i+1] = v = v * base % mod

	
	def get(self, l, r):
		return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

	def concatenate(self, l1, r1, l2, r2):
		return (self.get(l1, r1) * self.pw[r2-l2] + self.get(l2, r2)) % self.mod


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
if n == 1:
	print(0, a[0]^b[0])
	sys.exit()
x = [a[n-1]^a[0]]
y = [b[n-1]^b[0]]
for i in range(n-1):
	x.append(a[i]^a[i+1])
	y.append(b[i]^b[i+1])

rh1_x, rh1_y = RollingHash(x, BASE, MOD1), RollingHash(y, BASE, MOD1)
rh2_x, rh2_y = RollingHash(x, BASE, MOD2), RollingHash(y, BASE, MOD2)
for k in range(n):
	if rh1_y.concatenate(n-k, n, 0, n-k) == rh1_x.get(0, n) and rh2_y.concatenate(n-k, n, 0, n-k) == rh2_x.get(0, n):
		print(k, a[0]^b[(n-k)%n])

Solution (Python):
import sys
BASE, MOD1, MOD2 = (1<<30), (1<<61)-1, (1<<31)-1

class RollingHash():
	def __init__(self, s, base, mod):
		self.mod = mod
		self.pw = pw = [1]*(len(s)+1)

		l = len(s)
		self.h = h = [0]*(l+1)

		v = 0
		for i in range(l):
			h[i+1] = v = (v * base + s[i]) % mod
		v = 1
		for i in range(l):
			pw[i+1] = v = v * base % mod

	
	def get(self, l, r):
		return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

	def concatenate(self, l1, r1, l2, r2):
		return (self.get(l1, r1) * self.pw[r2-l2] + self.get(l2, r2)) % self.mod


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
if n == 1:
	print(0, a[0]^b[0])
	sys.exit()
x = [a[n-1]^a[0]]
y = [b[n-1]^b[0]]
for i in range(n-1):
	x.append(a[i]^a[i+1])
	y.append(b[i]^b[i+1])

rh1_x, rh1_y = RollingHash(x, BASE, MOD1), RollingHash(y, BASE, MOD1)
rh2_x, rh2_y = RollingHash(x, BASE, MOD2), RollingHash(y, BASE, MOD2)
for k in range(n):
	if rh1_y.concatenate(n-k, n, 0, n-k) == rh1_x.get(0, n) and rh2_y.concatenate(n-k, n, 0, n-k) == rh2_x.get(0, n):
		print(k, a[0]^b[(n-k)%n])

Solution (Python):

class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)

        l = len(s)
        self.h = h = [0]*(l+1)

        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + s[i]) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod
N=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[a[i%N]^a[(i+1)%N] for i in range(2*N)]
d=[b[i]^b[(i+1)%N] for i in range(N)]
P=RollingHash(c,97,10**9+7)
Q=RollingHash(d,97,10**9+7)

for k in range(N):
    if P.get(k,k+N)==Q.get(0,N):
        x=b[0]^a[k]
        print(k,x)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines




N = int(readline())

A = list(map(int,readline().split()))
B = list(map(int,readline().split()))

def convert(A):
    return [x ^ y for x,y in zip(A,A[1:])] + [A[-1] ^ A[0]]

C = convert(A); D = convert(B)

def Z_algorithm(S):
    
    N=len(S)
    arr = [0]*N
    arr[0] = N
    i,j = 1,0
    while i<N:
        while i+j<N and S[j]==S[i+j]:
            j += 1
        arr[i]=j
        if not j:
            i += 1
            continue
        k = 1
        while i+k<N and k+arr[k]<j:
            arr[i+k] = arr[k]
            k += 1
        i += k; j -= k
    return arr

Z = Z_algorithm(D + [-1] + C + C)[N+1:N+N+1]

K = [i for i,x in enumerate(Z) if x == N]
X = [A[k] ^ B[0] for k in K]

print('\n'.join('{} {}'.format(k,x) for k,x in zip(K,X)))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines




N = int(readline())

A = list(map(int,readline().split()))
B = list(map(int,readline().split()))

def convert(A):
    return [x ^ y for x,y in zip(A,A[1:])] + [A[-1] ^ A[0]]

C = convert(A); D = convert(B)

def Z_algorithm(S):
    
    N=len(S)
    arr = [0]*N
    arr[0] = N
    i,j = 1,0
    while i<N:
        while i+j<N and S[j]==S[i+j]:
            j += 1
        arr[i]=j
        if not j:
            i += 1
            continue
        k = 1
        while i+k<N and k+arr[k]<j:
            arr[i+k] = arr[k]
            k += 1
        i += k; j -= k
    return arr

Z = Z_algorithm(D + [-1] + C + C)[N+1:N+N+1]

K = [i for i,x in enumerate(Z) if x == N]
X = [A[k] ^ B[0] for k in K]

print('\n'.join('{} {}'.format(k,x) for k,x in zip(K,X)))

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

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

    A.extend(A)
    mod1 = 10**9+7
    mod2 = 10**9+9
    b1 = 1007
    b2 = 2009
    H1 = H2 = 0
    for i in range(N-1):
        tmp = B[i] ^ B[i+1]
        
        H1 = (H1 + pow(b1, N-i-2, mod1) * tmp)%mod1
        H2 = (H2 + pow(b2, N-i-2, mod2) * tmp) % mod2

    h1 = h2 = 0
    for i in range(N-1):
        tmp = A[i] ^ A[i+1]
        
        h1 = (h1 + pow(b1, N-i-2, mod1) * tmp)%mod1
        h2 = (h2 + pow(b2, N-i-2, mod2) * tmp) % mod2
    
    if h1 == H1 and h2 == H2:
        print(0, A[0]^B[0])
    for k in range(1, N):
        tmp_plus = A[N+k-2] ^ A[N+k-1]
        tmp_minus = A[k-1] ^ A[k]
        
        h1 = ((h1 * b1)%mod1 + tmp_plus - (tmp_minus * pow(b1, N-1, mod1))%mod1) % mod1
        h2 = ((h2 * b2) % mod2 + tmp_plus - (tmp_minus * pow(b2, N-1, mod2)) % mod2) % mod2
        
        if h1 == H1 and h2 == H2:
            print(k, A[k] ^ B[0])


if __name__ == '__main__':
    main()

Solution (Python):

base = 123
mod = 10**9+7
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
base_m = pow(base, N-1, mod)
ans = [True]*N
for k in range(30):
    tmp = []
    mask = 1<<k
    a_k = []
    a_k_r = []
    b_k = []
    for i in range(N):
        if a[i]&mask:
            a_k.append(1)
            a_k_r.append(0)
        else:
            a_k.append(0)
            a_k_r.append(1)
        if b[i]&mask:
            b_k.append(1)
        else:
            b_k.append(0)
    b_hash = b_k[0]
    a_hash = a_k[0]
    a_hash_r = a_k_r[0]
    for i in range(1, N):
        b_hash = (b_hash*base+b_k[i])%mod
        a_hash = (a_hash*base+a_k[i])%mod
        a_hash_r = (a_hash_r*base+a_k_r[i])%mod
    for i in range(N):
        if a_hash == b_hash or a_hash_r == b_hash:
            pass
        else:
            ans[i] = False
        a_hash = ((a_hash-a_k[i]*base_m)*base+a_k[i])%mod
        a_hash_r = ((a_hash_r-a_k_r[i]*base_m)*base+a_k_r[i])%mod
for i in range(N):
    if ans[i]:
        x = a[i]^b[0]
        print(i, x)

Solution (Python):
N = int(input())
AS = list(map(int, input().split()))
BS = list(map(int, input().split()))

AXOR = [AS[i] ^ AS[(i+1) % N] for i in range(N)]
BXOR = [BS[i] ^ BS[(i+1) % N] for i in range(N)]

def getZarr(string, z): 
    n = len(string) 
  
    
    
    l, r, k = 0, 0, 0
    for i in range(1, n): 
  
        
        
        if i > r: 
            l, r = i, i 
  
            
            
            
            
            
            while r < n and string[r - l] == string[r]: 
                r += 1
            z[i] = r - l 
            r -= 1
        else: 
  
            
            
            k = i - l 
  
            
            
            
            
            if z[k] < r - i + 1: 
                z[i] = z[k] 
  
            
            
            else: 
  
                
                l = i 
                while r < n and string[r - l] == string[r]: 
                    r += 1
                z[i] = r - l 
                r -= 1

string = list(BXOR) + [-1] + list(AXOR) + list(AXOR)[:-1]
Z = [0 for i in range(len(string))]
getZarr(string, Z)

res = []
for i in range(N, len(string)):
    
    if (Z[i] >= N):
        
        res.append((i - N - 1, AS[i-N-1] ^ BS[0]))
res.sort()
for a, b in res:
    print(a, b)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines




N = int(readline())

A = list(map(int,readline().split()))
B = list(map(int,readline().split()))

def convert(A):
    return [x ^ y for x,y in zip(A,A[1:])] + [A[-1] ^ A[0]]

C = convert(A); D = convert(B)

def Z_algorithm(S):
    
    N=len(S)
    arr = [0]*N
    arr[0] = N
    i,j = 1,0
    while i<N:
        while i+j<N and S[j]==S[i+j]:
            j += 1
        arr[i]=j
        if not j:
            i += 1
            continue
        k = 1
        while i+k<N and k+arr[k]<j:
            arr[i+k] = arr[k]
            k += 1
        i += k; j -= k
    return arr

Z = Z_algorithm(D + [-1] + C + C)[N+1:N+N+1]

K = [i for i,x in enumerate(Z) if x == N]
X = [A[k] ^ B[0] for k in K]

print('\n'.join('{} {}'.format(k,x) for k,x in zip(K,X)))