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):
from bisect import bisect_left
import sys
input = sys.stdin.readline

class Compress:

    def __init__(self, vs):
        self.xs = list(set(vs))
        self.xs.sort()

    def compress(self, x):
        return bisect_left(self.xs, x)

    def decompress(self, i):
        return self.xs[i]

def suffix_array(s):
    n = len(s)
    comp = Compress(s)
    t = [comp.compress(s[i]) for i in range(n)]
    cnt = [0] * n
    for i in range(n):
        cnt[t[i]] += 1
    for i in range(1, n):
        cnt[i] += cnt[i-1]
    p = [0] * n
    for i in range(n):
        cnt[t[i]] -= 1
        p[cnt[t[i]]] = i
    c = [0] * n
    cl = 0
    for i in range(1, n):
        if s[p[i]] != s[p[i-1]]:
            cl += 1
        c[p[i]] = cl

    pn = [0] * n
    cn = [0] * n
    h = 0
    while (1 << h) < n:
        for i in range(n):
            pn[i] = p[i] - (1 << h)
            if pn[i] < 0:
                pn[i] += n
        cnt = [0] * n
        for i in range(n):
            cnt[c[pn[i]]] += 1
        for i in range(1, n):
            cnt[i] += cnt[i-1]
        for i in range(n)[::-1]:
            cnt[c[pn[i]]] -= 1
            p[cnt[c[pn[i]]]] = pn[i]
        cn[p[0]] = 0
        cl = 0
        for i in range(1, n):
            cur = (c[p[i]], c[(p[i] + (1 << h)) % n])
            prev = (c[p[i-1]], c[(p[i-1] + (1 << h)) % n])
            if cur != prev:
                cl += 1
            cn[p[i]] = cl
        c, cn = cn, c
        h += 1
    return p


def bin_search(a, b, sa, lower):
    lb, ub = -1, N
    while ub - lb > 1:
        m = (lb + ub) // 2
        for i in range(N):
            j = (sa[m] + i) % N
            if a[i] < b[j]:
                ub = m
                break
            if a[i] > b[j]:
                lb = m
                break
        else:
            if lower:
                ub = m
            else:
                lb = m
    return ub

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)]
sa = suffix_array(d)
lb = bin_search(c, d, sa, True)
ub = bin_search(c, d, sa, False)
ans = []
for j in range(lb, ub):
    k = (N - sa[j]) % N
    x = a[k] ^ b[0]
    ans.append((k, x))
ans.sort()
for k, x in ans:
    print(k, x)

Solution (Python):
import re

N = int(input())
A = list(map(lambda x: bin(int(x))[2:], input().split()))
B = list(map(lambda x: bin(int(x))[2:], input().split()))
keta = max(max(map(len, A)), max(map(len, B)))


def xor(a, b):
    while keta > len(b):
        b = '0' + b
    while keta > len(a):
        a = '0' + a
    ret = ''
    for a_, b_ in zip(a, b):
        ret += '0' if a_ == b_ else '1'
    return ret


def create_table(pattern):
    table = [0 for _ in range(len(pattern)+1)]
    j = 0
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
        else:
            table[i] = j
            j = 0
    table[i+1] = j
    return table


def kmp_search(string, pattern):
    ret = []
    table = create_table(pattern)
    i = j = 0
    while i < len(string):
        if string[i] == pattern[j]:
            i += 1
            j += 1
        elif j == 0:
            i += 1
        else:
            j = table[j]
        if j == len(pattern):
            ret.append(i - j)
            j = table[j]
    else:
        return ret

def bm_search(string, pattern):
    ret = []
    pat_len = len(pattern)
    skip = [pat_len for _ in range(256)]
    for i in range(pat_len):
        skip[ord(pattern[i])] = pat_len - i - 1
    i = pat_len - 1
    while i < len(string):
        j = pat_len - 1
        while string[i] == pattern[j]:
            if j == 0:
                ret.append(i)
            i -= 1
            j -= 1
        i = i + max(skip[ord(string[i])], pat_len-j)
    return ret


C, D = [], []
for i in range(N-1):
    C.append(xor(A[i], A[i+1]))
    D.append(xor(B[i], B[i + 1]))
C.append(xor(A[-1], A[0]))
D.append(xor(B[-1], B[0]))
for k in kmp_search(D + D, C)[::-1]:
    if k == 0:
        continue
    print(N-k, int(xor(A[N-k], B[0]), 2))

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  

N = I()
a = LI()
b = LI()

if N == 1:
    print(0,a[0]^b[0])
    exit()

A = [a[i] ^ a[i+1] for i in range(N-1)]
A = A + [a[N-1] ^ a[0]] + A
B = [b[i] ^ b[i+1] for i in range(N-1)]





def f(mod,base):
    x = pow(base,N-1,mod)  

    d = 0  
    for i in range(N-1):
        d *= base
        d += B[i]
        d %= mod

    c = 0  
    for i in range(N-1):
        c *= base
        c += A[i]
        c %= mod

    for i in range(N):
        if c == d:
            print(i,a[i] ^ b[0])
        c *= base
        c -= A[i]*x
        c += A[i+N-1]
        c %= mod


f(10**9+7,1234)

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

def main():
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    mod=10**9+7
    """
    kを決めるかxを決めるか，
    kを決めればxが一意に決まり，N個試してO(N^2)
    xを決めればどうなるんだろう．
    ai全部にxorして，それをずらせばbになるならok．なんかもう少しうまくできそう．
    
    解説読んだ.
    全部のところに同じ操作をしている=>2箇所を使うことでうまく追加分を打ち消すことを考える．
    隣接2箇所を選びxorすれば xor xの部分が消える（もし+xなら2箇所選んで引けば良いというお話）
    
    shiftしたものが一致するか知る方法=>aとbなら，a*2の中にbがあるか探す．ここでKMP法やz-algoritmを使う
    
    
    """
    
    def Z(s):
        n=len(s)
        lcp=[0]*n
        lcp[0]=n
        L,R=0,0
        for i in range(1,n):
            if(i>=R): 
                L=i
                R=i
                while(R<n and s[R-L]==s[R]):
                    R+=1
                lcp[i]=R-L
            elif(lcp[i-L]<R-i): 
                lcp[i]=lcp[i-L]
            else: 
                L=i
                while(R<n and s[R-L]==s[R]):
                    R+=1
                lcp[i]=R-L
        return lcp
    
    N=I()
    a=LI()
    b=LI()
    a+=[a[0]]
    b+=[b[0]]
    
    
    a2=[0]*N
    b2=[0]*N
    for i in range(N):
        a2[i]=a[i+1]^a[i]
        b2[i]=b[i+1]^b[i]
        
    
    
    K=[]
    abb=a2+b2+b2
    L=Z(abb)
    
    for i in range(N,2*N,1):
        if L[i]>=N:
            K.append((2*N-i)%N)
            
    X=[]
    for k in K:
        x=b[0]^a[k]
        X.append(x)
    
    if K!=[]:
        K,X=zip(*sorted(zip(K,X)))
    else:
        exit()
        
    for i in range(len(K)):
        print(K[i],X[i])
        

    

main()

Solution (Python):
import os
import sys
import numpy as np

def z_algo(S):
    
    
    
    i, j, n = 1, 0, len(S)
    Z = np.zeros_like(S)
    Z[0] = n
    while i < n:
        while i+j < n and S[j] == S[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        Z[i] = j
        d = 1
        while i+d < n and d+Z[d] < j:
            Z[i+d] = Z[d]
            d += 1
        i += d
        j -= d
    return Z

def solve(N, A, B):
    Diff = np.empty(3*N, dtype=np.int64)
    Diff[0] = B[0] ^ B[-1]
    Diff[1:N] = B[1:] ^ B[:-1]
    Diff[N] = Diff[2*N] = A[0] ^ A[-1]
    Diff[N+1:2*N] = Diff[2*N+1:3*N] = A[1:] ^ A[:-1]
    Z = z_algo(Diff)[N:2*N]
    Ans = [(0,0)]*0
    for i in range(N):
        z = Z[i]
        if z >= N:
            Ans.append((i, B[0]^A[i]))
    if len(Ans):
        return np.array(Ans)
    return np.zeros((0, 2), dtype=np.int64)



numba_config = [
    [z_algo, "i8[:](i8[:])"],
    [solve, "i8[:,:](i8,i8[:],i8[:])"],
]
if sys.argv[-1] == "ONLINE_JUDGE":
    from numba import njit
    from numba.pycc import CC
    cc = CC("my_module")
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature)(func)
        cc.export(func.__name__, signature)(func)
    cc.compile()
    exit()
elif os.name == "posix":
    exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
else:
    from numba import njit
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature, cache=True)(func)
    print("compiled!", file=sys.stderr)



def main():
    N = int(input())
    A = np.array(input().split(), dtype=np.int64)
    B = np.array(input().split(), dtype=np.int64)
    Ans = solve(N, A, B).tolist()
    for k, x in Ans:
        print(f"{k} {x}")

main()

Solution (Python):
def z_algo(S):
    
    
    
    i, j, n = 1, 0, len(S)
    Z = [0] * n
    Z[0] = n
    while i < n:
        while i+j < n and S[j] == S[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        Z[i] = j
        d = 1
        while i+d < n and d+Z[d] < j:
            Z[i+d] = Z[d]
            d += 1
        i += d
        j -= d
    return Z


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A_diff = []
a2 = A[-1]
for a in A:
    A_diff.append(a^a2)
    a2 = a
B_diff = []
b2 = B[-1]
for b in B:
    B_diff.append(b^b2)
    b2 = b
A_diff_2 = A_diff + A_diff[:-1]
Z = z_algo(A_diff_2)
A_diff_str = "_".join(map(str, A_diff_2))
B_diff_str = "_".join(map(str, B_diff))
idx = A_diff_str.find(B_diff_str)
if idx==-1:
    exit()
idx = A_diff_str[:idx].count("_")
Ans = []
b0 = B[-idx]
for i, (z, a, b) in enumerate(zip(Z, A, B)):
    if z >= N:
        Ans.append([(idx+i)%N, a^b0])
        
        
Ans.sort()  
for k, x in Ans:
    print(f"{k} {x}")

Solution (Python):
LI = lambda: list(map(int, input().split()))

N = int(input())
A = LI()
B = LI()


def main():
    s = [A[i] ^ A[(i + 1) % N] for i in range(N)]
    t = [B[i] ^ B[(i + 1) % N] for i in range(N)] * 2
    w = [0] * N
    for i in range(1, N):
        j = w[i - 1]
        while j != 0 and s[i] != s[j]:
            j = w[j - 1]
        if s[i] == s[j]:
            w[i] = j + 1
        else:
            w[i] = 0

    k_list = []
    i, j = 0, 0
    while i < N:
        while j < N and t[i + j] == s[j]:
            j += 1
        if j == N:
            k_list.append(-i % N)
        if j == 0:
            i += 1
        else:
            i += j - w[j - 1]
    
    k_list.sort()
    for k in k_list:
        x = A[k] ^ B[0]
        print(k, x)


if __name__ == "__main__":
    main()

Solution (Python):

class RollingHash(object):
    """
        construct: O(N)
        query:
            hash: O(1)
            lcp: O(logN)
            search: O(N)
    """
    __base1 = 1007;
    __mod1 = 10 ** 9
    __base2 = 1009;
    __mod2 = 10 ** 7

    def __init__(self, s):
        n = len(s)
        self.__s = s
        self.__n = n
        b1 = self.__base1;
        m1 = self.__mod1
        b2 = self.__base2;
        m2 = self.__mod2
        H1, H2 = [0] * (n + 1), [0] * (n + 1)
        P1, P2 = [1] * (n + 1), [1] * (n + 1)
        for i in range(n):
            H1[i + 1] = (H1[i] * b1 + (s[i])) % m1
            H2[i + 1] = (H2[i] * b2 + (s[i])) % m2
            P1[i + 1] = P1[i] * b1 % m1
            P2[i + 1] = P2[i] * b2 % m2
        self.__H1 = H1
        self.__H2 = H2
        self.__P1 = P1
        self.__P2 = P2

    @property
    def str(self):
        return self.__s

    @property
    def len(self):
        return self.__n

    def hash(self, l, r=None):
        """
            l,r: int (0<=l<=r<=n)
            return (hash1,hash2) of S[l:r]
        """
        m1 = self.__mod1
        m2 = self.__mod2
        if r is None: r = self.__n
        assert 0 <= l <= r <= self.__n
        hash1 = (self.__H1[r] - self.__P1[r - l] * self.__H1[l] % m1) % m1
        hash2 = (self.__H2[r] - self.__P2[r - l] * self.__H2[l] % m2) % m2
        return hash1, hash2

    @classmethod
    def lcp(cls, rh1, rh2, l1, l2, r1=None, r2=None):
        """
            rh1,rh2: RollingHash object
            l1,l2,r1,r2: int 0<=l1<=r1<=r1.len, 0<=l2<=r2<=rh2.len
            return lcp length between rh1[l1:r1] and rh2[l2:r2]
        """
        if r1 is None: r1 = rh1.__n
        if r2 is None: r2 = rh2.__n
        assert 0 <= l1 <= r1 <= rh1.__n and 0 <= l2 <= r2 <= rh2.__n
        L = 0
        R = min(r1 - l1, r2 - l2)
        if rh1.hash(l1, l1 + R) == rh2.hash(l2, l2 + R): return R
        while R - L > 1:
            H = (L + R) // 2
            if rh1.hash(l1, l1 + H) == rh2.hash(l2, l2 + H): L = H
        else:
            R = H
        return L

    @classmethod
    def search(cls, pattern, text):
        """
        pattern,text: RollingHash object
        return list of index i's satisfying text[i:] starts with pattern
        """
        n = text.__n;
        m = pattern.__n
        res = []
        for i in range(n - m + 1):
            if text.hash(i, i + m) == pattern.hash(0, m):
                res.append(i)
        return res


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

    dA = [A[i] ^ A[(i + 1) % N] for i in range(N)]
    dB = [B[i] ^ B[(i + 1) % N] for i in range(N)]

    dA += dA
    
    RHa = RollingHash(dA)
    RHb = RollingHash(dB)
    query = RHb.hash(0, N - 1)
    ans = []
    for i in range(N):
        val = RHa.hash(i, i + N - 1)
        if val == query:
            ans.append((i, A[i] ^ B[0]))
    ans.sort()
    for k, x in ans:
        print(k, x)

if __name__ == "__main__":
    resolve()

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

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

    dA = [A[i] ^ A[(i + 1) % N] for i in range(N)]
    dB = [B[i] ^ B[(i + 1) % N] for i in range(N)]

    dA = dA + dA[:-1]
    
    K = KMP(dB).search(dA)
    for k in K:
        print(k, A[k] ^ B[0])

if __name__ == "__main__":
    resolve()

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

n = int(input())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))
C = [0]*(3*n)
for i in range(n):
  C[i] = B[i]^B[(i+1)%n]
  C[i+n] = A[i]^A[(i+1)%n]
  C[i+n+n] = C[i+n]

def z_algo(S):
    N = len(S)
    A = [0]*N
    A[0] = N
    i, j = 1, 0
    while i < N:
        while i+j < N and S[j] == S[i+j]:
            j += 1
        A[i] = j
        if not j:
            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  

P = z_algo(C)
for i, p in enumerate(P[n:n+n]):
  if p >= n:
    x = A[i]^B[0]
    print(i, x)

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

n = int(input())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))
C = [0]*(3*n)
for i in range(n):
  C[i] = B[i]^B[(i+1)%n]
  C[i+n] = A[i]^A[(i+1)%n]
  C[i+n+n] = C[i+n]

def z_algo(S):
    N = len(S)
    A = [0]*N
    A[0] = N
    i, j = 1, 0
    while i < N:
        while i+j < N and S[j] == S[i+j]:
            j += 1
        A[i] = j
        if not j:
            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  

P = z_algo(C)
for i, p in enumerate(P[n:n+n]):
  if p >= n:
    x = A[i]^B[0]
    print(i, x)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**89-1
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    a = LI()
    b = LI()

    ax = []
    bx = []
    for i in range(N):
        ax.append(a[i-1] ^ a[i])
        bx.append(b[i-1] ^ b[i])

    az = 0
    bz = 0
    m = 2**30
    for i in range(N):
        az = (az * m + ax[i]) % MOD
        bz = (bz * m + bx[i]) % MOD

    for i in range(N):
        if az == bz:
            print(i,a[i] ^ b[0])
        az = ((az - ax[i] * pow(m,N-1,MOD)) * m + ax[i]) % MOD

if __name__ == '__main__':
    main()

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

def KMP(sentence,word):
  ret=[]
  
  def make_table(word):
    n=len(word)
    table=[0]*(n+1)
    table[0]=-1
    j=-1
    for i in range(n):
      while j>=0 and word[i]!=word[j]:
        j=table[j]
      j+=1
      table[i+1]=j
    return table
  
  table=make_table(word)
  sentence_size=len(sentence)
  word_size=len(word)
  m=0
  i=0
  while m+i<sentence_size:
    if word[i]==sentence[m+i]:
      i+=1
      if i==word_size:
        ret.append(m)
        m=m+i-table[i]
        i=table[i]
    else:
      m=m+i-table[i]
      if i>0:
        i=table[i]
  return ret

n=int(input())
arr1=list(map(int,input().split()))
arr2=list(map(int,input().split()))
a=[]
b=[]
for i in range(n):
  a.append(arr1[i]^arr1[(i+1)%n])
  b.append(arr2[i]^arr2[(i+1)%n])
a=(a+a)[:-1]
ks=KMP(a,b)
if len(ks)==0:
  exit()
ans=[]
for k in ks:
  ans.append((k,arr2[0]^arr1[k%n]))
ans=sorted(ans,key=lambda x:x[1])
ans=sorted(ans,key=lambda x:x[0])
for k,x in ans:
  print(k,x)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
da = []
db = []
for i in range(n-1):
    da.append(A[i+1] ^ A[i])
    db.append(B[i+1] ^ B[i])
da.append(A[-1]^A[0])
db.append(B[-1]^B[0])
    
import random
M = 10**9+7
b = random.choice(range(M))
def rhash(s):
    import random
    ans = 0
    v = 1
    for item in s:
        ans += item*v
        v *= b
        ans %= M
        v %= M
    return ans

h = rhash(db)
g = rhash(da)
t = pow(b, n, M)
ans = []
for i in range(n):
    if h==g:

        ans.append((i,A[i]^B[0]))
    h *= b
    h = h - t*db[n-1-i] + db[n-1-i]
    h %= M
    
write("\n".join(" ".join(map(str, item)) for item in ans))

Solution (Python):

import sys


def bit_most(v):
    
    if v == 0:
        return 0
    else:
        return len(bin(v))-2


def z_algorithm(S):
    """Zアルゴリズム
    """
    N = len(S)
    Z = [0]*N

    c = 0
    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
    Z[0] = N
    return Z


def solve(N: int, a: "List[int]", b: "List[int]"):

    a1 = [0]*(2*N)
    b1 = [0]*N
    b2 = [0]*N
    k_cand = [True]*N
    for keta in range(bit_most(max(max(a), max(b)))+1):
        for i, aa in enumerate(a):
            a1[i] = a1[i+N] = (aa >> keta) & 1
        for i, bb in enumerate(b):
            b1[i] = v = (bb >> keta) & 1
            b2[i] = 1-v
        Z1 = z_algorithm(b1 + [-1] + a1)
        Z2 = z_algorithm(b2 + [-1] + a1)
        
        
        
        
        for i in range(N):
            if k_cand[i]:
                k_cand[i] = Z2[i+N+1] == N or Z1[i+N+1] == N
        

    for i in range(N):
        if k_cand[i]:
            print(i, b[0] ^ a[i])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  
    b = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  
    solve(N, a, b)


if __name__ == '__main__':
    main()

Solution (Python):

import sys


def z_algorithm(S):
    """Zアルゴリズム
    """
    N = len(S)
    Z = [0]*N

    c = 0
    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
    Z[0] = N
    return Z


def solve(N: int, a: "List[int]", b: "List[int]"):

    a1 = [0]*(2*N)
    b1 = [0]*N
    b2 = [0]*N
    k_cand = [True]*N
    for keta in range(30):
        for i, aa in enumerate(a):
            a1[i] = a1[i+N] = (aa >> keta) & 1
        for i, bb in enumerate(b):
            b1[i] = v = (bb >> keta) & 1
            b2[i] = 1-v
        Z1 = z_algorithm(b1 + [-1] + a1)
        Z2 = z_algorithm(b2 + [-1] + a1)
        
        
        
        
        for i in range(N):
            if k_cand[i]:
                k_cand[i] = Z2[i+N+1] == N or Z1[i+N+1] == N
        

    for i in range(N):
        if k_cand[i]:
            print(i, b[0] ^ a[i])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  
    b = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  
    solve(N, a, b)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
INF = float("inf")




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


def solve(N: int, a: "List[int]", b: "List[int]"):

    c = [a[i] ^ a[(i+1) % N]for i in range(N)]
    d = [b[i] ^ b[(i+1) % N]for i in range(N)]*2
    i = -1
    a1 = [0]*N
    a2 = [0]*N
    b1 = [0]*(2*N)
    k_cand = [True]*N
    setup_pw(2*N)
    
    
    for keta in range(30):
        mask = 1 << keta
        for i, aa in enumerate(a):
            a1[i] = (aa & mask) >> keta
            a2[i] = (~aa & mask) >> keta
        for i, bb in enumerate(b):
            b1[i] = (bb & mask) >> keta
            b1[i+N] = (bb & mask) >> keta
        P = rolling_hash(a1)
        Q = rolling_hash(a2)
        R = rolling_hash(b1)
        for i in range(N):
            if k_cand[i]:
                if not ((get(P, 0, N) == get(R, i, i+N)) or
                        (get(Q, 0, N) == get(R, i, i+N))):
                    k_cand[i] = False
        
        
        
        

    ans = []
    if len(k_cand) == 0:
        return
    if k_cand[0] == True:
        print(0, b[0] ^ a[0])
        for i, k in enumerate(k_cand[:0:-1], start=1):
            if k:
                print(i, b[0] ^ a[i])
    else:
        for i, k in enumerate(k_cand[::-1], start=1):
            if k:
                print(i, b[0] ^ a[i])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  
    b = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  
    solve(N, a, b)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
INF = float("inf")


B = 10**7+7
MOD = 10**9+7




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 z_algorithm(S):
    """Zアルゴリズム
    https://snuke.hatenablog.com/entry/2014/12/03/214243 の二番目のコード
    """
    N = len(S)
    Z = [0]*N

    c = 0
    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
    Z[0] = len(S)
    return Z


def zfindall(text, pattern, separator="$"):
    """テキストからパターンと一致する部分文字列を探す。
    開始インデックスを返す
    Zアルゴリズムを利用する
    """
    N = len(pattern)
    conc = pattern+separator+text
    Z = z_algorithm(conc)
    return {i-N-1 for i in range(len(conc)) if Z[i] == N}


def solve(N: int, a: "List[int]", b: "List[int]"):

    c = [a[i] ^ a[(i+1) % N]for i in range(N)]
    d = [b[i] ^ b[(i+1) % N]for i in range(N)]*2
    i = -1
    a1 = [0]*N
    a2 = [0]*N
    b1 = [0]*(2*N)
    k_cand = [True]*N
    for keta in range(30):
        mask = 1 << keta
        for i, aa in enumerate(a):
            a1[i] = (aa & mask) >> keta
            a2[i] = (~aa & mask) >> keta
        for i, bb in enumerate(b):
            b1[i] = (bb & mask) >> keta
            b1[i+N] = (bb & mask) >> keta
        P = RollingHash(a1, 97, MOD)
        Q = RollingHash(a2, 97, MOD)
        R = RollingHash(b1, 97, MOD)
        for i in range(N):
            if k_cand[i]:
                if not ((P.get(0, N) == R.get(i, i+N)) or
                        (Q.get(0, N) == R.get(i, i+N))):
                    k_cand[i] = False
        
        
        
        

    ans = []
    if len(k_cand) == 0:
        return
    if k_cand[0] == True:
        print(0, b[0] ^ a[0])
        for i, k in enumerate(k_cand[:0:-1], start=1):
            if k:
                print(i, b[0] ^ a[i])
    else:
        for i, k in enumerate(k_cand[::-1], start=1):
            if k:
                print(i, b[0] ^ a[i])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  
    b = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  
    solve(N, a, b)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
INF = float("inf")


B = 10**7+7
MOD = 10**9+7


def z_algorithm(S):
    """Zアルゴリズム
    https://snuke.hatenablog.com/entry/2014/12/03/214243 の二番目のコード
    """
    N = len(S)
    Z = [0]*N

    c = 0
    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
    Z[0] = len(S)
    return Z


def zfindall(text, pattern, separator="$"):
    """テキストからパターンと一致する部分文字列を探す。
    開始インデックスを返す
    Zアルゴリズムを利用する
    """
    N = len(pattern)
    conc = pattern+separator+text
    Z = z_algorithm(conc)
    return [i-N-1 for i in range(len(conc)) if Z[i] == N]


def solve(N: int, a: "List[int]", b: "List[int]"):

    c = [a[i] ^ a[(i+1) % N]for i in range(N)]
    d = [b[i] ^ b[(i+1) % N]for i in range(N)]*2
    i = -1
    k_cand = zfindall(d, c, separator=[-1])
    

    ans = []
    if len(k_cand) == 0:
        return
    if k_cand[0] % N == 0:
        print(0, b[0] ^ a[0])
        for k in k_cand[:0:-1]:
            if k < N:
                print(-k % N, b[0] ^ a[-k % N])
    else:
        for k in k_cand[::-1]:
            if k < N:
                print(-k % N, b[0] ^ a[-k % N])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  
    b = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  
    solve(N, a, b)


if __name__ == '__main__':
    main()

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

X = []
for a,b in zip(A,A[1:]):
    X.append(a ^ b)
X.append(A[-1] ^ A[0])

Y = []
for a,b in zip(B,B[1:]):
    Y.append(a ^ b)
Y.append(B[-1] ^ B[0])

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

za = z_algorithm(X + [-1] + Y + Y)
for i in range(N):
    if za[-N-i] == N:
        print(i, A[i]^B[0])

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
a+=a
b=list(map(int,input().split()))
aa=[a[i-1]^a[i] for i in range(1,n*2)]
bb=[b[i-1]^b[i] for i in range(1,n)]
s=bb+aa
from random import randint
roli_mod=1370757747362922367
roli_r=1
roli_table=[0]
roli_rr=1
for i in range(3*(n-1)):
  roli_table.append((roli_table[-1]+roli_rr*s[i])%roli_mod)
  roli_rr*=roli_r
  roli_rr%=roli_mod
def roli_hash(i,j):return ((roli_table[j+1]-roli_table[i]+roli_mod)%roli_mod)*pow(roli_r,roli_mod-1-i,roli_mod)%roli_mod
def roli_check(i1,j1,i2,j2):return roli_hash(i1,j1)==roli_hash(i2,j2)
ans=[]
for k in range(n-1,2*(n-1)+1):
  if roli_check(0,n-2,k,k+(n-1)-1):
    ans.append(k-(n-1))
for i in ans:
  print(i,a[i]^b[0])

Solution (Python):
def main():
    def z_algo(S):
        n, i, j = len(S), 1, 0
        a = [0]*n
        a[0] = n
        while i < n:
            while i+j < n and S[i+j] == S[j]:
                j += 1
            if not j:
                i += 1
                continue
            a[i], k = j, 1
            while a[k] < j-k and i+k < n:
                a[i+k] = a[k]
                k += 1
            i += k
            j -= k
        return a

    n = int(input())
    a, b = list(map(int, input().split())), list(map(int, input().split()))
    a1 = [a[i-1] ^ a[i] for i in range(n)]
    z = z_algo([b[i-1] ^ b[i] for i in range(n)]+a1+a1)
    memo = []
    for i in range(n):
        if z[n+i] >= n:
            memo.append(i)
    b0 = b[0]
    for i in memo:
        print(i, b0 ^ a[i])


main()