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: Time Limit Exceeded

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, num=1))
        bh.append(RollingHash(tb, num=1))
        bnh.append(RollingHash(tbn, num=1))

    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()))
    for r in slv(N, A, B):
        print(*r)

    # import random
    # N = 2 * 10**5
    # A = [random.randint(0, 1 << 30) for _ in range(N)]
    # B = [random.randint(0, 1 << 30) for _ in range(N)]
    # print(*slv(N, A, B), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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()))
    for r in slv(N, A, B):
        print(*r)

    # import random
    # N = 2 * 10**5
    # A = [random.randint(0, 1 << 30) for _ in range(N)]
    # B = [random.randint(0, 1 << 30) for _ in range(N)]
    # print(*slv(N, A, B), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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 = shift[i]-1
            head += max(1,shift[i])
            break
    else:
        x = b[0] ^ a[head]
        ans.append([head, x])
        start = shift[i]-1
        head += max(1,shift[i])


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

Submission status: Time Limit Exceeded

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(1,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 = mp[i+1]-(i+1)
            head += mp[i+1]
            break
    else:
        x = b[0] ^ a[head]
        ans.append([head, x])
        start = i-mp[i+1]
        head += mp[i+1]


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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
###F Prob.ABC 150#######解き直し Result:[TLE####
import numpy as np
import copy
N = int(input())
a_list = list(map(int,input().split()))
b_list = list(map(int,input().split()))


def list_rotate(list_num):
    copy_list = copy.deepcopy(list_num)
    copy_list = copy_list[1:]
    copy_list.append(copy.deepcopy(list_num[0]))
    
    return copy_list

k_counter = 0
XOR_list = np.zeros_like(a_list)
k_x_list = []

while(True):

    for i in range(N):
        XOR_list[i] = (b_list[i])^(a_list[i])
        
    
    XOR_uniset = list(set(XOR_list))
    if (len(XOR_uniset) == 1):
        
        k_x_list.append((k_counter,XOR_uniset[0]))
        
    a_list = list_rotate(a_list)
    k_counter += 1
        
    if (k_counter >= N):
        break
        
        
for kx in k_x_list:
    print("{} {}".format(kx[0],kx[1]))

Submission status: Time Limit Exceeded

Solution code:
###F Prob.ABC 150##
import numpy as np
import copy
N = int(input())
a_list = list(map(int,input().split()))
b_list = list(map(int,input().split()))


def list_rotate(list_num):
    copy_list = copy.deepcopy(list_num)
    copy_zero = copy_list[0]
    copy_list = copy_list[1:]
    copy_list.append(copy_zero)
    
    return copy_list

k_counter = 0
XOR_list = np.zeros_like(a_list)
k_x_list = []

while(True):
    
    XOR_list = np.zeros_like(a_list)

    for i in range(N):
        XOR_list[i] = (b_list[i])^(a_list[i])
        
    
    XOR_uniset = list(set(XOR_list))
    if (len(XOR_uniset) == 1):
        
        k_x_list.append((k_counter,XOR_uniset[0]))
        
    a_list = list_rotate(a_list)
    k_counter += 1
        
    if (k_counter >= N):
        break
        
        
for kx in k_x_list:
    print("{} {}".format(kx[0],kx[1]))

Submission status: Time Limit Exceeded

Solution code:
###F Prob.ABC 150##
import numpy as np
import copy
N = int(input())
a_list = list(map(int,input().split()))
b_list = list(map(int,input().split()))

not_x_flag   = 0
not_all_flag = 0
def list_rotate(list_num):
    copy_list = copy.deepcopy(list_num)
    copy_zero = copy_list[0]
    copy_list = copy_list[1:]
    copy_list.append(copy_zero)
    
    return copy_list

k_counter = 0
XOR_list = np.zeros_like(a_list)
k_x_list = []

while(True):
    
    XOR_list = np.zeros_like(a_list)

    for i in range(N):
        XOR_list[i] = (b_list[i])^(a_list[i])
        
    
    XOR_uniset = list(set(XOR_list))
    if (len(XOR_uniset) != 1):
        a_list = list_rotate(a_list)
        k_counter += 1
        
    else:
        k_x_list.append((k_counter,XOR_uniset[0]))
        a_list = list_rotate(a_list)
        k_counter += 1
        
    if (k_counter >= N):
        break
        
        
for kx in k_x_list:
    print("{} {}".format(kx[0],kx[1]))

Submission status: Time Limit Exceeded

Solution code:
###F Prob.ABC 150##
import numpy as np
import copy
N = int(input())
a_list = list(map(int,input().split()))
b_list = list(map(int,input().split()))

not_x_flag   = 0
not_all_flag = 0
def list_rotate(list_num):
    copy_list = copy.deepcopy(list_num)
    copy_zero = copy_list[0]
    copy_list = copy_list[1:]
    copy_list = np.append(copy_list,copy_zero)
    
    return copy_list

k_counter = 0
XOR_list = np.zeros_like(a_list)
k_x_list = []
a_list = np.array(a_list)
b_list = np.array(b_list)
while(True):
    
    XOR_list = np.zeros_like(a_list)

    for i in range(N):
        XOR_list[i] = (b_list[i])^(a_list[i])
        
    
    XOR_uniset = list(set(XOR_list))
    if (len(XOR_uniset) != 1):
        a_list = list_rotate(a_list)
        k_counter += 1
        
    else:
        k_x_list.append((k_counter,XOR_uniset[0]))
        a_list = list_rotate(a_list)
        k_counter += 1
        
    if (k_counter >= N):
        break
        
        
for kx in k_x_list:
    print("{} {}".format(kx[0],kx[1]))

Submission status: Time Limit Exceeded

Solution code:
def divisors(M):#Mの約数列 O(n^(0.5+e))
    import math
    d=[]
    i=1
    while math.sqrt(M)>=i:
        if M%i==0:
            d.append(i)
            if i**2!=M:
                d.append(M//i)
        i=i+1
    d.sort()
    return d

N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
A=[a[i]^a[i-1] for i in range(0,N)]
B=[b[i]^b[i-1] for i in range(0,N)]
d=divisors(N)
perioda=N
for i in range(0,len(d)):
    test=[A[(j+d[i])%N] for j in range(0,N)]
    if test==A:
        perioda=min(perioda,d[i])

periodb=N
for i in range(0,len(d)):
    test=[B[(j+d[i])%N] for j in range(0,N)]
    if test==B:
        periodb=min(periodb,d[i])

if perioda==periodb:
    A=A[:perioda]
    B=B[:periodb]
    kouho=[]
    for i in range(0,len(B)):
        if A[i]==B[0]:
            kouho.append(i)
    ans=-1
    for i in range(0,len(kouho)):
        test=[A[(j+kouho[i])%perioda] for j in range(0,perioda)]
        if test==B:
            ans=kouho[i]
            break
    if ans!=-1:
        for i in range(0,N//perioda):
            print(ans+perioda*i,a[ans+perioda*i]^b[0])

Submission status: Time Limit Exceeded

Solution code:
def divisors(M):#Mの約数列 O(n^(0.5+e))
    import math
    d=[]
    i=1
    while math.sqrt(M)>=i:
        if M%i==0:
            d.append(i)
            if i**2!=M:
                d.append(M//i)
        i=i+1
    d.sort()
    return d

import numpy as np
N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
A=np.array([a[i]^a[i-1] for i in range(0,N)])
B=np.array([b[i]^b[i-1] for i in range(0,N)])
d=divisors(N)
perioda=N
for i in range(0,len(d)):
    test=np.roll(A,-d[i])
    if all(test==A):
        perioda=min(perioda,d[i])

periodb=N
for i in range(0,len(d)):
    test=np.roll(B,-d[i])
    if all(test==B):
        periodb=min(periodb,d[i])

if perioda==periodb:
    A=A[:perioda]
    B=B[:periodb]
    ans=-1
    for i in range(0,perioda):
        if all(A==B):
            ans=i
            break
        A=np.roll(A,-1)
    if ans!=-1:
        for i in range(0,N//perioda):
            print(ans+perioda*i,a[ans+perioda*i]^b[0])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
A=[a[i]^a[i-1] for i in range(0,N)]
B=[b[i]^b[i-1] for i in range(0,N)]

ca=0
for i in range(0,N):
    ca=ca|A[i]
    ca=ca<<35
ca=ca>>35
cb=0
for i in range(0,N):
    cb=cb|B[i]
    cb=cb<<35
cb=cb>>35

for k in range(0,N):
    if ca==cb:
        print(k,a[k]^b[0])
    x=0
    for i in range(0,35):
        if cb &1==1:
            x+=pow(2,i)
        cb=cb>>1
    x=x<<35*(N-1)
    cb=cb|x

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

def main():
	N = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]

	xor_a = [a[i] ^ a[(i+1) % N] for i in range(len(a))]
	xor_b = [b[i] ^ b[(i+1) % N] for i in range(len(b))]

	kmp = KmpSearch(xor_a + xor_a, xor_b)

	start = 0
	ans = []
	x = []
	while True:
		k = kmp.search(start)
		if k == -1 or k == len(a):
			break
		ans.append(k)
		start = k + 1
		x.append(a[0 + k] ^ b[0])

	for i in range(len(ans)):
		print(str(ans[i]) + " " + str(x[i]))

class KmpSearch:
	def __init__(self, target, pattern):
		self.target = target
		self.pattern = pattern
		self.__table = self.__create_kmp_table()

	def search(self, start=0):
		if len(self.pattern) > len(self.target):
			return -1

		i = start
		p = 0
		while i < len(self.target):
			if self.pattern[p] == self.target[i]:
				i += 1
				p += 1

				if p == len(self.pattern):
					return i - p
			elif p == 0:
				i += 1
			else:
				p = self.__table[p]

		return -1

	def __create_kmp_table(self):
		table = [0 for x in range(len(self.pattern))]

		j = 0
		for i in range(1, len(self.pattern)):
			table[i] = j
			if self.pattern[j] == self.pattern[i]:
				j += 1
			else:
				j = 0

		return table

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

def main():
	N = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]

	xor_a = [a[i] ^ a[(i+1) % N] for i in range(len(a))]
	xor_b = [b[i] ^ b[(i+1) % N] for i in range(len(b))]

	bm = BMSearch(xor_a + xor_a, xor_b)

	start = 0
	ans = []
	x = []
	while True:
		k = bm.search(start)
		if k == -1 or k == len(a):
			break
		ans.append(k)
		start = k + 1
		x.append(a[0 + k] ^ b[0])

	for i in range(len(ans)):
		print(str(ans[i]) + " " + str(x[i]))

class BMSearch:
	def __init__(self, target, pattern):
		self.target = target
		self.pattern = pattern
		self.__table = self.__create_BM_table()

	def search(self, start=0):

		if len(self.pattern) > len(self.target):
			return -1

		i = len(self.pattern) - 1 + start
		p = len(self.pattern) - 1
		while i < len(self.target):
			if self.pattern[p] == self.target[i]:
				i -= 1
				p -= 1

				if p == -1:
					return i + 1
			else:
				t = self.__table[self.target[i]] if (self.target[i] in self.__table) else len(self.pattern)
				i += max(t, len(self.pattern) - p)
				p = len(self.pattern) - 1

		return -1

	def __create_BM_table(self):
		table = {}

		for i in range(len(self.pattern)):
			table[self.pattern[i]] = len(self.pattern) - i - 1

		return table

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

n = int(input())
A = np.array(input().split(), dtype=np.int64)
B = np.array(input().split(), dtype=np.int64)
for i in range(0, -n, -1):
  C = np.roll(A, i) ^ B
  if np.array_equiv(C, C[-1]):
    print(-i, C[-1])

Submission status: Time Limit Exceeded

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

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

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

    C = xor_next(A)
    D = xor_next(B)
    
    pos = []
    for k in range(N):
        if C[k:N] + C[0:k+N-N] == D:
            pos.append(k)

    ans = []
    for i in pos:
        ans.append((i, A[i] ^ B[0]))

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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]

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

Submission status: Time Limit Exceeded

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]

for i in range(N):
  if difa[i:N]+difa[0:i] == difb:
    print(i,a[i]^b[0])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = np.array(input().split(),dtype=int)
b = np.array(input().split(),dtype=int)

k = []
c = [a[i]^a[i-1] for i in range(n)]
d = [b[i]^b[i-1] for i in range(n)]

i = 0
m = 0
while i < n:
    if c[i] == d[0]:
        for j in range(1,n):
            flag = True
            if m == 0 and i+j < n and c[(i+j)%n] == d[0]:
                m = i+j
            if not c[(i+j)%n] == d[j]:
                flag = False
                break
        if flag:
            k.append(i)
    i = max([i+1,m])
    m = 0

for i in k:
    x = a[i]^b[0]
    print(i,x)