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):

import sys
input = sys.stdin.readline

class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base = 1009
        self.mod = (1 << 61) - 1
        self.hash = [0] * (self.length + 1)
        self.pow = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash[i+1] = (self.hash[i] + s[i]) * self.base % self.mod
            self.pow[i+1] = self.pow[i] * self.base % self.mod

    def get(self, l, r):
        t = self.hash[r] - self.hash[l] * self.pow[r-l] % self.mod
        t = (t + self.mod) % self.mod
        return t

n = int(input())
a = [int(item) for item in input().split()]
b = [int(item) for item in input().split()]
a = a + a

diffa = []
diffb = []
for i in range(1, len(a)):
    diffa.append(a[i] ^ a[i-1])
for i in range(1, len(b)):
    diffb.append(b[i] ^ b[i-1])

RHa = RollingHash(diffa)
RHb = RollingHash(diffb)
query = RHb.get(0, n-1)
ans = []
for i in range(n):
    val = RHa.get(i, i+n-1)
    if val == query:
        ans.append((i, a[i] ^ b[0]))
ans.sort()
for k, x in ans:
    print(k, x)

Solution (Python):

import sys
input = sys.stdin.readline

class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base = 1009
        self.mod = (1 << 61) - 1
        self.hash = [0] * (self.length + 1)
        self.pow = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash[i+1] = (self.hash[i] + s[i]) * self.base % self.mod
            self.pow[i+1] = self.pow[i] * self.base % self.mod

    def get(self, l, r):
        t = self.hash[r] - self.hash[l] * self.pow[r-l] % self.mod
        t = (t + self.mod) % self.mod
        return t

n = int(input())
a = [int(item) for item in input().split()]
b = [int(item) for item in input().split()]
a = a + a

diffa = []
diffb = []
for i in range(1, len(a)):
    diffa.append(a[i] ^ a[i-1])
for i in range(1, len(b)):
    diffb.append(b[i] ^ b[i-1])

RHa = RollingHash(diffa)
RHb = RollingHash(diffb)
query = RHb.get(0, n-1)
ans = []
for i in range(n):
    val = RHa.get(i, i+n-1)
    if val == query:
        ans.append((i, a[i] ^ b[0]))
ans.sort()
for k, x in ans:
    print(k, x)

Solution (Python):
def Z_algorithm(s):
    n = len(s)
    A = [n] + [0] * (n-1)
    i, j = 1, 0
    while i < n:
        while i + j < n and s[j] == s[i+j]:
            j += 1
        A[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < n and k + A[k] < j:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A

N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
AA = [A[i] ^ A[i-1] for i in range(N)]
BB = [B[i] ^ B[i-1] for i in range(N)]

T = Z_algorithm(AA + [-1] + BB + BB)
for i in range(N, 0, -1):
    if T[N+i+1] >= N:
        print(N-i, A[-i%N] ^ B[0])

Solution (Python):
def KMP_table(WW):
    TT = [-1] * (len(WW)+2)
    ii = 2
    jj = 0
    TT[0] = -1
    TT[1] = 0
    while ii < len(WW)+1:
        if WW[ii - 1] == WW[jj]:
            TT[ii] = jj + 1
            ii += 1
            jj += 1
        elif jj > 0:
            jj = TT[jj]
        else:
            TT[ii] = 0
            ii += 1
    return TT

def KMP(T):
    ret = -1
    
    m = 0
    i = 0
    RE = []
    while m + i < len(S):
        if W[i] == S[m + i]:
            i += 1
            if i == len(W):
                RE.append(m)
                m = m + i - T[i]
                if i > 0:
                    i = T[i]
        else:
            m = m + i - T[i]
            if i > 0:
                i = T[i]
    return RE

N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
S = ([A[i] ^ A[i-1] for i in range(N)] * 2)[:-1]
W = [B[i] ^ B[i-1] for i in range(N)]

T = KMP_table(W)
for i in KMP(T):
    print(i, A[i] ^ B[0])

Solution (Python):
def Z_algorithm(s):
    n = len(s)
    A = [n] + [0] * (n-1)
    i, j = 1, 0
    while i < n:
        while i + j < n and s[j] == s[i+j]:
            j += 1
        A[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < n and k + A[k] < j:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A

N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
AA = [A[i] ^ A[i-1] for i in range(N)]
BB = [B[i] ^ B[i-1] for i in range(N)]

T = Z_algorithm(AA + BB + BB)
for i in range(N, 0, -1):
    if T[N+i] >= N:
        print(N-i, A[-i%N] ^ B[0])

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
AA = [A[i] ^ A[i-1] for i in range(N)]
BB = [B[i] ^ B[i-1] for i in range(N)]
P = 8128812823
K = 8128
invK = pow(K, P-2, P)
KN = pow(K, N, P)

s = 0
for i in range(N):
    s = (s * K + AA[i]) % P

t = 0
for b in BB:
    t = (t * K + b) % P
ans = 0
for i in range(N)[::-1]:
    if t == s:
        j = N - 1 - i
        print(j, A[j] ^ B[0])
    t = (t + BB[i] * (KN - 1)) * invK % P

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
AA = [A[i] ^ A[i-1] for i in range(N)]
BB = [B[i] ^ B[i-1] for i in range(N)]
P = 8128812881288171
K = 8128
invK = pow(K, P-2, P)
KN = pow(K, N, P)

s = 0
for i in range(N):
    s = (s * K + AA[i]) % P

t = 0
for b in BB:
    t = (t * K + b) % P
ans = 0
for i in range(N)[::-1]:
    if t == s:
        j = N - 1 - i
        print(j, A[j] ^ B[0])
    t = (t + BB[i] * (KN - 1)) * invK % P

Solution (Python):
def solve(n, aaa, bbb):
    ccc = [a1 ^ a2 for a1, a2 in zip(aaa, aaa[1:])] + [aaa[-1] ^ aaa[0]]
    ddd = [b1 ^ b2 for b1, b2 in zip(bbb, bbb[1:])] + [bbb[-1] ^ bbb[0]]

    ans = []

    m = 2147483647
    g = 1000000007
    s = 0
    for c in ccc:
        s = (s * g + c) % m
    t = 0
    for d in ddd:
        t = (t * g + d) % m
    u = pow(g, n, m) - 1
    for i in range(n):
        if s == t:
            ans.append((i, aaa[i] ^ bbb[0]))
        s = (s * g - ccc[i] * u) % m
    ans.sort()
    return ans


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
ans = solve(n, aaa, bbb)
print(''.join('{} {}\n'.format(*answer) for answer in ans))

Solution (Python):
class KMP:
    def __init__(self, P):
        self.P = P
        self.N = len(P)
        self.T = [0] * (self.N + 1)
        self._compile()

    def _compile(self):
        j = 0
        self.T[0] = -1
        for i in range(1, self.N):
            self.T[i] = j
            j += 1 if self.P[i] == self.P[j] else -j
        self.T[self.N] = j

    def search(self, S):
        NS = len(S)
        i = m = 0
        A = []
        while m + i < NS:
            if self.P[i] == S[m + i]:
                i += 1
                if i != self.N:
                    continue
                A.append(m)
            m += i - self.T[i]
            i = max(0, self.T[i])
        return A

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = [A[i]^A[(i+1)%N] for i in range(N)]
D = [B[i]^B[(i+1)%N] for i in range(N)]
C = C + C[:-1]
K = KMP(D).search(C)

for k in K:
    print(k, A[k]^B[0])

Solution (Python):
class KMP:
    def __init__(self, P):
        self.P = P
        self.N = len(P)
        self.T = [0] * (self.N + 1)
        self._compile()

    def _compile(self):
        j = 0
        self.T[0] = -1
        for i in range(1, self.N):
            self.T[i] = j
            j += 1 if self.P[i] == self.P[j] else -j
        self.T[self.N] = j

    def search(self, S):
        NS = len(S)
        i = m = 0
        A = []
        while m + i < NS:
            if self.P[i] == S[m + i]:
                i += 1
                if i != self.N:
                    continue
                A.append(m)
            m += i - self.T[i]
            i = max(0, self.T[i])
        return A

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = [A[i]^A[(i+1)%N] for i in range(N)]
D = [B[i]^B[(i+1)%N] for i in range(N)]
C = C + C[:-1]
K = KMP(D).search(C)

for k in K:
    print(k, A[k]^B[0])

Solution (Python):
class KMP:
    def __init__(self, P):
        self.P = P
        self.N = len(P)
        self.T = [0] * (self.N + 1)
        self._compile()

    def _compile(self):
        j = 0
        self.T[0] = -1
        for i in range(1, self.N):
            self.T[i] = j
            j += 1 if self.P[i] == self.P[j] else -j
        self.T[self.N] = j

    def search(self, S):
        NS = len(S)
        i = m = 0
        A = []
        while m + i < NS:
            if self.P[i] == S[m + i]:
                i += 1
                if i != self.N:
                    continue
                A.append(m)
            m += i - self.T[i]
            i = max(0, self.T[i])
        return A

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = [A[i]^A[(i+1)%N] for i in range(N)]
D = [B[i]^B[(i+1)%N] for i in range(N)]
C = C + C[:-1]
K = KMP(D).search(C)
for k in K:
    print(k, A[k]^B[0])

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

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



shift=[0]*(N+1)
k=1
l=0
while k<N:
    if AX[k]==AX[l]:
        k+=1
        l+=1
        shift[k]=l
    elif l>0:
        l=shift[l]
    else:
        k+=1
        shift[k]=0


ans=[]
ai=bi=0
Z=0
while bi<N:
    
    if BX2[bi+ai]==AX[ai]:
        ai+=1
        if ai==N-1:
            print(bi,A[bi]^B[0])
            ans.append((bi+1)%N)
            bi+=ai-shift[ai]
            ai=shift[ai]
    else:
        bi+=1 if ai==0 else ai-shift[ai]
        ai=shift[ai]

Solution (Python):
def z_algorithm(s):
    """文字列sが与えられたとき、各iについて「SとS[i:|S|-1]の最長共通接頭辞の長さ」
    を記録した配列 A を O(|S|) で構築するアルゴリズムです。"""

    a = [0] * len(s)
    i = 1
    j = 0
    a[0] = len(s)
    while i < len(s):
        while i + j < len(s) and s[j] == s[i+j]:
            j += 1
        a[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(s) and k + a[k] < j:
            a[i+k] = a[k]
            k += 1
        i += k
        j -= k
    return a


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

p = [0] * n
q = [0] * n
for i in range(n):
    p[i] = a[i] ^ a[(i + 1) % n]
    q[i] = b[i] ^ b[(i + 1) % n]

test = q + p + p
res = z_algorithm(test)
ans = []
for i in range(n, 2*n):
    if res[i] >= n:
        ans.append((i - n, a[(i - n) % n] ^ b[0]))
ans = sorted(ans)

for i in ans:
    print(*i)

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


def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg


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


    BAA = []
    for i in range(n-1):
        BAA.append(b[i]^b[i+1])
    BAA.append(b[0]^b[-1])

    BAA.append(-1)

    for i in range(n-1):
        BAA.append(a[i]^a[i+1])
    BAA.append(a[0]^a[-1])
    for i in range(n-1):
        BAA.append(a[i]^a[i+1])
    BAA.append(a[0]^a[-1])

    z = Z_algorithm(BAA)

    for k in range(n):
        if z[n+k+1] >= n:
            print(k,b[0]^a[k])

if __name__ == '__main__':
    main()

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


def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg


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


BAA = []
for i in range(n-1):
    BAA.append(b[i]^b[i+1])
BAA.append(b[0]^b[-1])

BAA.append(-1)

for i in range(n-1):
    BAA.append(a[i]^a[i+1])
BAA.append(a[0]^a[-1])
for i in range(n-1):
    BAA.append(a[i]^a[i+1])
BAA.append(a[0]^a[-1])

z = Z_algorithm(BAA)

for k in range(n):
    if z[n+k+1] >= n:
        print(k,b[0]^a[k])

Solution (Python):
n = int(input())


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


a2 = [a[i]^a[i-1] for i in range(n)]
b2 = [b[i]^b[i-1] for i in range(n)]
b2 = b2+b2






base = 37; mod = 10**9 + 9
pw = None
def rolling_hash(s):
    l = len(s)
    h = [0]*(l + 1)
    v = 0
    for i in range(l):
        h[i+1] = v = (v * base + s[i]) % mod
    return h

def setup_pw(l):
    global pw
    pw = [1]*(l + 1)
    v = 1
    for i in range(l):
        pw[i+1] = v = v * base % mod
def get(h, l, r):
    return (h[r] - h[l] * pw[r-l]) % mod

setup_pw(n*2)
bh = rolling_hash(b2)
ah = rolling_hash(a2)
ans = []

get_a = get(ah,0,n)
for k in range(n):
    if get(bh,k,k+n) == get_a:
        ans.append(k)
for k in ans:
    x = b[k]^a[0]
    print(k,x)

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


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

h = 10**11+7
b = 10**7+7

H = [1]
for _ in range(N):
    H.append((H[-1]*b)%h)

allSum = 0
for i in range(N):
    allSum = (allSum + H[i]) % h

ok = [True]*N
ans = [0]*N

L = 30
for l in range(L):
    HashA = 0
    for i, a in enumerate(A):
        if (1<<l)&a:
            HashA = (HashA + H[i]) % h

    HashB = 0
    for i, a in enumerate(B):
        if (1<<l)&a:
            HashB = (HashB + H[i]) % h
    
    for k in range(N):
        if (HashA+HashB)%h == allSum:
            ans[k] += (1<<l)
        elif HashA != HashB:
            ok[k] = False
        HashB = (HashB * b) % h
        if (1<<l)&B[-k-1]:
            HashB = (HashB + h - H[N] + 1) % h

for k in range(N):
    if ok[k]:
        print(k, ans[k])

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
input = sys.stdin.readline


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

h = 10**11+7
b = 10**7+7

H = [1]
for _ in range(N):
    H.append((H[-1]*b)%h)

C = []
D = []
for i in range(N):
    C.append(A[i-1]^A[i])
    D.append(B[i-1]^B[i])


HashA = 0
for i, a in enumerate(C):
    HashA = (HashA + a*H[i]%h) % h

HashB = 0
for i, a in enumerate(D):
    HashB = (HashB + a*H[i]%h) % h

ans = []
for k in range(N):
    if HashA == HashB:
        ans.append(k)
    HashB = (HashB * b) % h
    HashB = (HashB + (1-H[N])*D[-k-1] % h) % h

for k in ans:
    print(k, A[k]^B[0])

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


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

h = 10**11+7
b = 10**7+7

H = [1]
for _ in range(N):
    H.append((H[-1]*b)%h)

allSum = 0
for i in range(N):
    allSum = (allSum + H[i]) % h

ok = [True]*N
ans = [0]*N

C = []
D = []
for i in range(N):
    C.append(A[i-1]^A[i])
    D.append(B[i-1]^B[i])


HashA = 0
for i, a in enumerate(C):
    HashA = (HashA + a*H[i]%h) % h

HashB = 0
for i, a in enumerate(D):
    HashB = (HashB + a*H[i]%h) % h

ans = []
for k in range(N):
    if HashA == HashB:
        ans.append(k)
    HashB = (HashB * b) % h
    HashB = (HashB + (1-H[N])*D[-k-1] % h) % h

for k in ans:
    print(k, A[k]^B[0])

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


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

h = 10**11+7
b = 10**7+7

H = [1]
for _ in range(N):
    H.append((H[-1]*b)%h)

allSum = 0
for i in range(N):
    allSum = (allSum + H[i]) % h

ok = [True]*N
ans = [0]*N

C = []
D = []
for i in range(N):
    C.append(A[i-1]^A[i])
    D.append(B[i-1]^B[i])


HashA = 0
for i, a in enumerate(C):
    HashA = (HashA + a*H[i]%h) % h

HashB = 0
for i, a in enumerate(D):
    HashB = (HashB + a*H[i]%h) % h

ans = []
for k in range(N):
    if HashA == HashB:
        ans.append(k)
    HashB = (HashB * b) % h
    HashB = (HashB + (1-H[N])*D[-k-1] % h) % h

for k in ans:
    print(k, A[k]^B[0])

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, *lst = map(int, read().split())
al = lst[:n]
bl = lst[n:]


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


a = convert(al)
b = convert(bl)


def Z_algorithm(s):
    n = len(s)
    z = [0] * n
    l, r = 0, 0
    for i in range(1, n):
        if i <= r:
            z[i] = z[i - l] if z[i - l] < r - i else r - i - 1
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] - 1 > r:
            l, r = i, i + z[i] - 1
    return z


Z = Z_algorithm(b + [-1] + a + a)[n + 1:n + n + 1]

K = [i for i, x in enumerate(Z) if x == n]
X = [al[k] ^ bl[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, *lst = map(int, read().split())
al = lst[:n]
bl = lst[n:]


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


a = convert(al)
b = convert(bl)


def Z_algorithm(s):
    n = len(s)
    z = [0] * n
    l, r = 0, 0
    for i in range(1, n):
        if i <= r:
            z[i] = min(r - i - 1, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] - 1 > r:
            l, r = i, i + z[i] - 1
    return z


Z = Z_algorithm(b + [-1] + a + a)[n + 1:n + n + 1]

K = [i for i, x in enumerate(Z) if x == n]
X = [al[k] ^ bl[0] for k in K]

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

Solution (Python):
def partial_match_table(word):
    table = [0] * (len(word) + 1)
    table[0] = -1
    i, j = 0, 1
    while j < len(word):
        matched = word[i] == word[j]
        if not matched and i > 0:
            i = table[i]
        else:
            if matched:
                i += 1
            j += 1
            table[j] = i
    return table

def kmp_search(text, word):
    table = partial_match_table(word)
    i, p = 0, 0
    results = []
    while i < len(text) and p < len(word):
        if text[i] == word[p]:
            i += 1
            p += 1
            if p == len(word):
                p = table[p]
                results.append((i-len(word), i))
        elif p == 0:
            i += 1
        else:
            p = table[p]
    return results

N, = map(int, input().split())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))
A = []
B = []
for i in range(2*N-1):
    A.append(As[i%N] ^ As[(i+1)%N])
    if i < N:
        B.append(Bs[i%N] ^ Bs[(i+1)%N])
for k, l in kmp_search(A, B):
    print(k, As[k] ^ Bs[0])

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]






def ZAlgorithm(aa):
    target = aa
    
    len_t = len(target)
    lcp = [-1] * len_t
    top = 1  
    left = 0  
    right = 0  
    lcp[0] = 0
    while top < len_t:
        
        while top + right < len_t and target[right] == target[top + right]:
            right += 1
        
        lcp[top] = right
        left = 1
        
        if right == 0:
            top += 1
            continue
        
        while left + lcp[left] < right and left < right:
            lcp[top + left] = lcp[left]
            left += 1
        
        top += left
        right -= left
        left = 0  
    return lcp

def main():
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    inf = pow(2, 31)
    n = II()
    aa = LI()
    bb = LI()
    ax = [aa[i - 1] ^ aa[i] for i in range(n)]
    bx = [bb[i - 1] ^ bb[i] for i in range(n)]
    
    
    ll = ZAlgorithm(bx + [inf] + ax + ax[:-1])
    
    for shift, lcp in enumerate(ll[n + 1:]):
        if lcp == n: print(shift, aa[shift] ^ bb[0])

main()

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
条件を満たすとき
a_{(i+k) mod N} xor X = b_i
a_{(i+k+1) mod N} xor X = b_{i+1}が成り立つ
よって,a_{(i+k) mod N} xor a_{(i+k+1) mod N} = b_i xor b_{i+1}
各iについてb_i xor b_{i+1}を求めたリストをB,
数列aを2つ繋げて,a_i xor a_{i+1}を求めたリストをA,
BとAを繋げたリストをCとする.
Z_algorithmを用いるとSとS[i:|S|-1]の最長共通接頭辞の長さがO(N)で出せるので,
CにZ_algorithmを用いると,最初のBとAの共通部分列の長さが出せる.
共通部分列の長さがN以上のとき,条件を満たす.
"""

def Z_algorithm(s):
    n = len(s)
    Z = [0]*n
    Z[0] = n
    i,j = 1,0
    while i < n:
        while i+j < n and s[j] == s[i+j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
 
        
        while i+k < n and k+Z[k] < j:
            Z[i+k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z

n = I()
a = LI()
b = LI()

x = [a[i%n]^a[(i+1)%n] for i in range(2*n)]
y = [b[i%n]^b[(i+1)%n] for i in range(n)]
z = Z_algorithm(y+x)
for i in range(n,2*n):
    if z[i] >= n:
        k = i-n
        x = a[k] ^ b[0]
        print(k,x)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def Z_algorithm(s):
    n = len(s)
    Z = [0]*n
    Z[0] = n
    i,j = 1,0
    while i < n:
        while i+j < n and s[j] == s[i+j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
 
        
        while i+k < n and k+Z[k] < j:
            Z[i+k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z

n = I()
a = LI()
b = LI()

x = [a[i%n]^a[(i+1)%n] for i in range(2*n)]
y = [b[i%n]^b[(i+1)%n] for i in range(n)]
z = Z_algorithm(y+x)
for i in range(n,2*n):
    if z[i] >= n:
        k = i-n
        x = a[k] ^ b[0]
        print(k,x)

Solution (Python):
import sys
from operator import xor
from functools import reduce
readline = sys.stdin.readline

mod = 10**18+3
base = 10**9+9
def rollinghash(S):
    N = len(S)
    has = [0]*(N+1)
    power = [1]*(N+1)
    for i in range(N):
        s = S[i]
        has[i+1] = (has[i]*base + s)%mod
        power[i+1] = power[i]*base%mod
    return has, power
 
def rh(i, j):
    return (has[j] - has[i]*power[j-i])%mod

def rotate(k):
    pass

N = int(readline())
A = list(map(int, readline().split()))
B = list(map(int, readline().split()))
CA = [a1^a2 for a1, a2 in zip(A, A[1:])]
CA.append(A[0]^A[-1])
CB = [a1^a2 for a1, a2 in zip(B, B[1:])]
CB.append(B[0]^B[-1])

rA = [1+ca for ca in CA]
has, power = rollinghash(rA)
R = rh(0, N)
    
HA = [None]*N
suf = pow(base, N-1, mod)
for i in range(N):
    HA[i] = R
    R = ((R-suf*rA[i])*base + rA[i])%mod

rB = [1+cb for cb in CB]
has, power = rollinghash(rB)
R = rh(0, N)

Ans = []
for i in range(N):
    if HA[i] == R:
        Ans.append((i, A[i]^B[0]))

if Ans:
    print('\n'.join(' '.join(map(str, a)) for a in Ans))

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,96,10**9+7)
Q=RollingHash(d,96,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):
def check(ccc, ddd, e, ans):
    m = 2147483647
    g = 1000000007
    for l in range(e):
        cl = ccc[l]
        if any(c != cl for c in ccc[l::e]):
            return
        dl = ddd[l]
        if any(d != dl for d in ddd[l::e]):
            return
    s = 0
    for c in ccc[:e]:
        s = (s * g + c) % m
    t = 0
    for d in ddd[:e]:
        t = (t * g + d) % m
    u = pow(g, e, m)
    for h in range(e):
        if s == t:
            bh = bbb[h]
            ans.update(((i - h) % n, aaa[i] ^ bh) for i in range(0, n, e))
            return
        t = (t * g + ddd[(e + h) % n] - ddd[h] * u) % m


def solve(n, aaa, bbb):
    ccc = [a1 ^ a2 for a1, a2 in zip(aaa, aaa[1:])] + [aaa[-1] ^ aaa[0]]
    ddd = [b1 ^ b2 for b1, b2 in zip(bbb, bbb[1:])] + [bbb[-1] ^ bbb[0]]

    ans = set()

    e = 1
    while e * e <= n:
        if n % e != 0:
            e += 1
            continue
        check(ccc, ddd, e, ans)
        check(ccc, ddd, n // e, ans)
        e += 1

    return ans


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
ans = solve(n, aaa, bbb)
print(''.join('{} {}\n'.format(*answer) for answer in sorted(ans)))

Solution (Python):
import sys
BASE, MOD = 80408696819889532, (1<<61)-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])

rh_x, rh_y = RollingHash(x, BASE, MOD), RollingHash(y, BASE, MOD)
for k in range(n):
	if rh_y.concatenate(n-k, n, 0, n-k) == rh_x.get(0, n):
		print(k, a[0]^b[(n-k)%n])

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:
            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):
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

C = [a1^a2 for a1, a2 in zip(A, A[1:])] + [A[0]^A[-1]]
C = C + C
D = [b1^b2 for b1, b2 in zip(B, B[1:])] + [B[0]^B[-1]]

K = []
k = 0
while k < N:
  next_k = k
  is_first = True
  for i in range(N):
    if is_first and i>0 and C[k+i]==D[0]:
      next_k = k + i
      is_first = False
    if C[k+i] != D[i]:
      if next_k == k:
        k = k + i + 1
      else:
        if D[k+i-next_k] == C[k+i]:
          k = next_k
        else:
          k = k + i + 1
      break
  
  if i == N-1:
    K.append(k)
    if next_k == k:
      break
    else:
      k = next_k
      if len(K) == 2:
        diff = K[1] - K[0]
        while K[-1] < N:
          K.append(K[-1]+diff)
      
        _ = K.pop()
        break

for k in K:
  print(k, A[k]^B[0])