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.



Sample input:
3
0 2 1
1 2 3


Sample output:
1 3

Submission status: Wrong Answer

Solution code:
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


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

print(A)
print(B)
print(C)
print(D)

Submission status: Wrong Answer

Solution code:
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]]
    
    #隣接二項のxorがrotateしてることが必要
    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]
        
    #a2*2の中にb2があるか見たい，abbに対してZしてi>=Nで，LCPがN以上の場所
    
    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)
        
    for i in range(len(K)):
        print(K[i],X[i])
        

    

main()

Submission status: Wrong Answer

Solution code:
from random import randrange
from itertools import chain
def solve(A,B):
    N = len(A)

    temp = []
    for k in range(16):
        i = randrange(N)
        b = B[i]
        temp.append([a^b for a in chain(A[i:],A[:i])])
    for k in range(16):
        i = randrange(N)
        a = A[i]
        j = (i+1)%N
        temp.append([a^b for b in chain(reversed(B[:j]),reversed(B[j:]))])

    shifts = [(i,temp[0][i]) for i in range(N) if all(temp[0][i] == l[i] for l in temp)]

    if len(shifts) < 5000:
        nshifts = []
        for k,x in shifts:
            if all(a^b==x for a,b in zip(chain(A[k:],A[:k]),B)):
                nshifts.append((k,x))
        shifts = nshifts

    return '\n'.join(f'{a} {b}' for a,b in shifts)




if __name__ == '__main__':
    N = int(input())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    print(solve(A,B))

Submission status: Wrong Answer

Solution code:
from random import randrange
from itertools import chain
def solve(A,B):
    N = len(A)

    temp = []
    for k in range(32):
        i = randrange(N)
        b = B[i]
        temp.append([a^b for a in chain(A[i:],A[:i])])

    shifts = [(i,temp[0][i]) for i in range(N) if all(temp[0][i] == l[i] for l in temp)]

    if len(shifts) < 5000:
        nshifts = []
        for k,x in shifts:
            if all(a^b==x for a,b in zip(chain(A[k:],A[:k]),B)):
                nshifts.append((k,x))
        shifts = nshifts

    return '\n'.join(f'{a} {b}' for a,b in shifts)




if __name__ == '__main__':
    N = int(input())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    print(solve(A,B))

Submission status: Wrong Answer

Solution code:
from random import randrange
from itertools import chain
def solve(A,B):
    N = len(A)

    temp = []
    for k in range(32):
        i = randrange(N)
        b = B[i]
        temp.append([a^b for a in chain(A[i:],A[:i])])

    shifts = [(i,temp[0][i]) for i in range(N) if all(temp[0][i] == l[i] for l in temp)]

    if len(shifts) < 500:
        nshifts = []
        for k,x in shifts:
            if all(a^b==x for a,b in zip(chain(A[k:],A[:k]),B)):
                nshifts.append((k,x))
        shifts = nshifts

    return '\n'.join(f'{a} {b}' for a,b in shifts)




if __name__ == '__main__':
    N = int(input())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    print(solve(A,B))

Submission status: Wrong Answer

Solution code:
from random import randrange
from itertools import chain
def solve(A,B):
    N = len(A)

    temp = []
    for k in range(32):
        i = randrange(N)
        b = B[i]
        temp.append([a^b for a in chain(A[i:],A[:i])])

    shifts = [(i,temp[0][i]) for i in range(N) if all(temp[0][i] == l[i] for l in temp)]

    if len(shifts) < 32:
        nshifts = []
        for k,x in shifts:
            if all(a^b==x for a,b in zip(chain(A[k:],A[:k]),B)):
                nshifts.append((k,x))
        shifts = nshifts

    shifts.sort()
    return '\n'.join(f'{a} {b}' for a,b in shifts)




if __name__ == '__main__':
    N = int(input())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    print(solve(A,B))

Submission status: Wrong Answer

Solution code:
from random import randrange
from itertools import chain
def solve(A,B):
    N = len(A)

    m = 32
    temp = []
    for k in range(m):
        i = randrange(N)
        b = B[i]
        temp.append([a^b for a in chain(A[i:],A[:i])])

    shifts = [(i,temp[0][i]) for i in range(N) if all(temp[0][i] == l[i] for l in temp)]

    if len(shifts) < 16:
        nshifts = []
        for k,x in shifts:
            if all(a^b==x for a,b in zip(chain(A[k:],A[:k]),B)):
                nshifts.append((k,x))
        shifts = nshifts

    return '\n'.join(f'{a} {b}' for a,b in shifts)




if __name__ == '__main__':
    N = int(input())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    print(solve(A,B))

Submission status: Wrong Answer

Solution code:
from random import randrange
from itertools import chain
def solve(A,B):
    N = len(A)

    m = 64
    temp = []
    for k in range(m):
        i = randrange(N)
        b = B[i]
        temp.append([a^b for a in chain(A[i:],A[:i])])

    shifts = [(i,temp[0][i]) for i in range(N) if all(temp[0][i] == l[i] for l in temp)]

    return '\n'.join(f'{a} {b}' for a,b in shifts)




if __name__ == '__main__':
    N = int(input())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    print(solve(A,B))

Submission status: Wrong Answer

Solution code:
from random import randrange
from itertools import chain
def solve(A,B):
    N = len(A)

    m = 32
    temp = []
    for k in range(m):
        i = randrange(N)
        b = B[i]
        temp.append([a^b for a in chain(A[i:],A[:i])])

    shifts = [(i,temp[0][i]) for i in range(N) if all(temp[0][i] == temp[j][i] for j in range(m))]

    return '\n'.join(f'{a} {b}' for a,b in shifts)




if __name__ == '__main__':
    N = int(input())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    print(solve(A,B))

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**61-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()

Submission status: Wrong Answer

Solution code:
def main():
    mod, pow3, p = 2**31-1, [1]*200001, 1
    i3 = pow(3, mod-2, mod)
    for i in range(1, 200001):
        pow3[i] = p = p*3 % mod

    def rolling_hash(seq):
        h = sum([(i+1)*j for i, j in zip(seq, pow3[:-1])]) % mod
        H0s = [0]*n
        for i, j in enumerate(seq):
            H0s[i] = h
            h = (h-j-1+(j+1)*pn)*i3 % mod
        return H0s

    n = int(input())
    a, b = list(map(int, input().split())), list(map(int, input().split()))
    pn, memo = pow3[n], []

    a1 = [a[i-1] ^ a[i] for i in range(n)]
    b1 = [b[i-1] ^ b[i] for i in range(n)]
    b_hash = sum([(i+1)*j for i, j in zip(b1, pow3[:-1])]) % mod
    A1 = rolling_hash(a1)
    for i, j in enumerate(A1):
        if j == b_hash:
            memo.append(i)
    a0 = a1[0]
    for i in memo:
        x = a0 ^ b1[i]
        print(i, x)


main()

Submission status: Wrong Answer

Solution code:
def main():
    mod = 2**61-1
    pow3 = [1]*400001
    pow3i = [1]*200001
    p = 1
    i3 = pow(3, mod-2, mod)
    for i in range(1, 400001):
        p = p*3 % mod
        pow3[i] = p
    p = 1
    for i in range(1, 200001):
        p = p*i3 % mod
        pow3i[i] = p

    class rolling_hash():
        def __init__(self, seq):
            seq_size = len(seq)  # 文字列の長さ
            self.H0s = [0]*(seq_size+1)  # 先頭からi-1文字目までのハッシュ値
            H0s, p = self.H0s, 0
            for i, j in enumerate(seq):
                p = (p+(j+1)*pow3[i]) % mod
                H0s[i+1] = p

        def calc_hash(self, l, r):  # l文字目からr-1文字目までのハッシュ値
            H0s = self.H0s
            return ((H0s[r]-H0s[l])*pow3i[l]) % mod

    def rolling_hash2(seq):
        p = 0
        for i, j in enumerate(seq):
            p += (j+1)*pow3[i] % mod
        return p % mod

    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    m = max(a+b)
    a += a
    a1 = [0]*(2*n)
    a2 = [0]*(2*n)
    b1 = [0]*n
    memo = [0]*n
    cnt = n

    for k in range(len(bin(m))-2):
        k2 = 2**k
        for i, j in enumerate(a):
            p = j & k2
            a1[i] = p
            a2[i] = p ^ k2
        for i, j in enumerate(b):
            b1[i] = j & k2
        b_hash = rolling_hash2(b1)
        A1 = rolling_hash(a1)
        A2 = rolling_hash(a2)
        for i, j in enumerate(memo):
            if j is None:
                continue
            elif A1.calc_hash(i, i+n) == b_hash:
                pass
            elif A2.calc_hash(i, i+n) == b_hash:
                memo[i] += k2
            else:
                memo[i] = None
                cnt -= 1
        if cnt == 0:
            print(-1)
            return

    for i, j in enumerate(memo):
        if j is not None:
            print(i, j)


main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()

def Z(S):
    n = len(S)
    res = [0] * n
    res[0] = n
    l = r = 0
    for i in range(1, n):
        if res[i - l] < r - i: # 過去の結果が全て使える
            res[i] = res[i - l]
        else:
            l = i
            r = max(i, r) # i < r ならば過去の結果が一部使える
            while r < n and S[r - l] == S[r]: r += 1
            res[i] = r - l
    return res

def resolve():
    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)]
    prefix = Z(C + D + D)
    res = []
    for k in range(n):
        if prefix[n + k] >= n:
            print((n - k) % n, A[0] ^ B[k])
resolve()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = s[i]
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

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

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

    @staticmethod
    def gen(a, b, num):
        result = set()
        while 1:
            import random
            import math
            random.seed()
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


def slv(N, A, B):
    L = max(max(A), max(B)).bit_length()
    ba = []
    bb = []
    ah = []
    bh = []
    bnh = []
    for i in range(L):
        ta = []
        tb = []
        tbn = []
        for a, b in zip(A, B):
            ta.append(a >> i & 1)
            tb.append(b >> i & 1)
            tbn.append(tb[-1] ^ 1)
        ba.append(ta)
        bb.append(tb)
        ah.append(RollingHash(ta))
        bh.append(RollingHash(tb))
        bnh.append(RollingHash(tbn))

    ans = []
    for k in range(N):
        x = 0
        for i in range(L):
            l = ah[i].calc(k, N)
            r = ah[i].calc(0, k)
            if l == bh[i].calc(0, N-k) and r == bh[i].calc(N-k, N):
                pass
            elif l == bnh[i].calc(0, N-k) and r == bnh[i].calc(N-k, N):
                x += 1 << i
            else:
                break
        else:
            ans.append((k, x))

    return ans



def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    print(*slv(N, A, B), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

axor=[0]*n
bxor=[0]*n

for i in range(n-1):
    axor[i] = a[i] ^ a[i+1]
    bxor[i] = b[i] ^ b[i+1]

axor[-1] = a[0] ^ a[-1]
bxor[-1] = b[0] ^ b[-1]

def MP(it):
    n = len(it)
    res = [0]*(n+1)
    res[0] = -1
    j = -1
    for i in range(n):
        while j >= 0 and it[i] != it[j]:
            j = res[j]
        j += 1
        res[i+1] = j
    return res

mp = MP(bxor)
shift = [0]*n
for i in range(n):
    shift[i] = i+1 - mp[i+1]
txt = axor + axor
head = 0
ans = list()
start = 0
while head < n:
    for i in range(start,n):
        if bxor[i] != txt[head+i]:
            start = i+1-shift[i]
            head += max(1,shift[i])
            break
    else:
        x = b[0] ^ a[head]
        ans.append([head, x])
        start = i+1-shift[i]
        head += max(1,shift[i])


for k,x in ans:
    print(k,x)

Submission status: Wrong Answer

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

axor=[0]*n
bxor=[0]*n

for i in range(n-1):
    axor[i] = a[i] ^ a[i+1]
    bxor[i] = b[i] ^ b[i+1]

axor[-1] = a[0] ^ a[-1]
bxor[-1] = b[0] ^ b[-1]

def MP(it):
    n = len(it)
    res = [0]*(n+1)
    res[0] = -1
    j = -1
    for i in range(n):
        while j >= 0 and it[i] != it[j]:
            j = res[j]
        j += 1
        res[i+1] = j
    return res

mp = MP(bxor)
for i in range(len(mp)):
    mp[i] = i - mp[i]
txt = axor + axor
head = 0
ans = list()
start = 0
while head < n:
    for i in range(start,n):
        if bxor[i] != txt[head+i]:
            start = (i+1)-mp[i+1]
            head += mp[i]
            break
    else:
        x = b[0] ^ a[head]
        ans.append([head, x])
        start = (i+1)-mp[i+1]
        head += mp[i]


for k,x in ans:
    print(k,x)

Submission status: Wrong Answer

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

axor=[0]*n
bxor=[0]*n

for i in range(n-1):
    axor[i] = a[i] ^ a[i+1]
    bxor[i] = b[i] ^ b[i+1]

axor[-1] = a[0] ^ a[-1]
bxor[-1] = b[0] ^ b[-1]

def MP(it):
    n = len(it)
    res = [0]*(n+1)
    res[0] = -1
    j = -1
    for i in range(n):
        while j >= 0 and it[i] != it[j]:
            j = res[j]
        j += 1
        res[i+1] = j
    return res

mp = MP(bxor)
for i in range(len(mp)):
    mp[i] = i - mp[i]
txt = axor + axor
head = 0
ans = list()
start = 0
while head < n:
    for i in range(start,n):
        if bxor[i] != txt[head+i]:
            start = (i+1)-mp[i]
            head += mp[i]
            break
    else:
        x = b[0] ^ a[head]
        ans.append([head, x])
        start = (i+1)-mp[i]
        head += mp[i]


for k,x in ans:
    print(k,x)

Submission status: Wrong Answer

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

ans = []

for i in range(n):
    xr=a[i]^b[0]
    for j in range(n):
        if i+j >= n:
            if xr == a[(j % i)]^b[j]:
                if j == n-1:
                    ans.append([i, xr])
            else:
                # if i==5 and xr==5:
                #     print(i%j, j,xr)
                break
        else:
            if xr == a[i+j]^b[j]:
                if j == n-1:
                    ans.append([i, xr])
            else:
                break
    
ans.sort()
for i, j in ans:
    print(i, j)

Submission status: Wrong Answer

Solution code:
####################################### Define
maxN = int(4e5 + 100)
a = [0] * maxN
b = [0] * maxN
ans = [0] * maxN
####################################### Functions
def solve() :
    L = R = -1
    for i in range(1, n + 1) :
        if i > R :
            L = R = i
            while R + 1 <= 2 * n and (a[i] ^ b[1]) == (a[R + 1] ^ b[R - L + 2]): R += 1
#            print(a[i] ^ b[1], a[R + 1] ^ b[R - L + 2], "\n")
            ans[i] = R - L + 1
        else :
            k = i - L
            if ans[k] < R - i + 1 : ans[i] = ans[k]
            else :
                L = i
                while R + 1 <= 2 * n and (a[i] ^ b[1]) == (a[R + 1] ^ b[R - L + 2]): R += 1
                ans[i] = R - L + 1
####################################### Main
n = int(input())
inp = input().split()
for i in range(1, n + 1) : a[i] = int(inp[i - 1])
for i in range(n + 1, 2 * n + 1) : a[i] = a[i - n]
inp = input().split()
for i in range(1, n + 1) : b[i] = int(inp[i - 1])
for i in range(n + 1, 2 * n + 1) : b[i] = b[i - n]

solve()

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from fractions import gcd
from functools import lru_cache

#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
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)]

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

######Combination######
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

######Factorization######
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

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

#############
# Main Code #
#############

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]

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from fractions import gcd
from functools import lru_cache

#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
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)]

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

######Combination######
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

######Factorization######
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

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

#############
# Main Code #
#############

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 len(set(difa)) == len(set(difb)) == 1:
  print("dummy")
  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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from fractions import gcd
from functools import lru_cache

#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
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)]

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

######Combination######
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

######Factorization######
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

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

#############
# Main Code #
#############

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]

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:
  print("dummy")
  d = memo[1]-memo[0]
  k = memo[1]+d
  while k < N:
    print(k,a[k]^b[0])
    k += d

Submission status: Wrong Answer

Solution code:
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, a[0] ^ b[x]))
rres.sort(key = lambda x: (x[0], x[1]))
for r in rres: print(*r)

Submission status: Wrong Answer

Solution code:
# F
import sys
input = sys.stdin.readline
import numpy as np
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
#N=10**5
#a=list(map(int, np.random.rand(N)*2**30))
#b=list(map(int, np.random.rand(N)*2**30))
#b=a[-N//2:]+a[:N//2]
diffs = []
for lis in [a, b]:
    lis_tmp = np.array(lis[1:]+[lis[0]])
    diffs.append(list(abs(lis_tmp-np.array(lis))))

ad = diffs[0]
bd = (diffs[1]*2)[:-1]

ans_set = []
find_str = ad[0]
start_pos = 0
Searching = True
try:
    find_ind = bd[start_pos:].index(find_str)+start_pos
except:
    Searching = False
while(Searching and find_ind < N):
    bd_tmp=bd[find_ind:find_ind+N]
    if np.count_nonzero(np.array(ad)-np.array(bd_tmp))==0:
        k = N-find_ind
        x = abs(b[find_ind]-a[0])
        ans_set.append([k % N, x])
    start_pos = find_ind+1
    if start_pos >= N:
        break
    try:
        find_ind = bd[start_pos:].index(find_str)+start_pos
    except:
        break

ans_set = sorted(ans_set, key=lambda x: (x[0], x[1]))

for k, x in ans_set:
    print(k, x)