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:
import sys
import numpy as np
readline = sys.stdin.readline
write = sys.stdout.write

def main():
  N = int(readline())
  a = np.array(list(map(int, readline().split())))
  b = np.array(list(map(int, readline().split())))
  NA = np.arange(N)

 # for k in range(N):
 #   pass
    #r = np.bitwise_xor(a[(NA+k)%N], b)
    #if np.all(r == r[0]):
    #  pass
    #  #print(k, r[0])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
  N = int(readline())
  a = np.array(list(map(int, readline().split())))
  b = np.array(list(map(int, readline().split())))
  NA = np.arange(N)

  for k in range(N):
    pass
    #r = np.bitwise_xor(a[(NA+k)%N], b)
    #if np.all(r == r[0]):
    #  pass
    #  #print(k, r[0])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
  N = int(readline())
  a = np.array(list(map(int, readline().split())))
  b = np.array(list(map(int, readline().split())))
  NA = np.arange(N)

  for k in range(N):
    r = np.bitwise_xor(a[(NA+k)%N], b)
    if np.all(r == r[0]):
      pass
      #print(k, r[0])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
  N = int(readline())
  a = np.array(list(map(int, readline().split())))
  b = np.array(list(map(int, readline().split())))
  NA = np.array(range(N), dtype=int)
  
  buf = ''
  for k in range(N):
    r = np.bitwise_xor(a[(NA+k)%N], b)
    if np.all(r == r[0]):
      buf += '{} {}¥n'.format(k, r[0])
  write(buf)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline

def main():
  N = int(readline())
  a = list(map(int, readline().split()))
  b = list(map(int, readline().split()))
  buf = []
  
  for k in range(N):
    c = []
    last = None
    for i in range(N):
      r = c.append(a[(i+k)%N] ^ b[i])
      if last != r:
      	break
      last = r
    else:
      buf.append((k, c[0]))
  for d in buf:
    print(d[0], d[1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def check(ccc, ddd, e, ans):
    m = 2147483647
    g = 1000000007
    for l in range(e):
        cl = ccc[l]
        if any(c != cl for c in ccc[l::e]):
            return
        dl = ddd[l]
        if any(d != dl for d in ddd[l::e]):
            return
    s = 0
    for c in ccc[:e]:
        s = (s * g + c) % m
    t = 0
    for d in ddd[:e]:
        t = (t * g + d) % m
    u = pow(g, e, m)
    for h in range(e):
        if s == t:
            bh = bbb[h]
            ans.update(((i - h) % n, aaa[i] ^ bh) for i in range(0, n, e))
            return
        t = (t * g + ddd[(e + h) % n] - ddd[h] * u) % m


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

    ans = set()

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

    return ans


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

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
a = np.array(list(map(int, input().split())))
b = np.array(list(map(int, input().split())))
NA = np.array(range(N))

buf = []
for k in range(N):
  g = a[list(np.array(range(k, N+k)) % N)] 
  if sum(g - g[0]) == 0:
      buf.append((k, g[0]))
for d in buf:
  print(*d)

Submission status: Wrong Answer

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

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

print(C)
print(D)

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

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
def Z(S):
    res = [0]*len(S)
    res[0] = len(S)
    i = 1
    j = 0
    while i < len(S):
        while i+j < len(S) and S[j] == S[i+j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < len(S) and k+res[k] < j:
            res[i+k] = res[k]
            k += 1
        i += k
        j -= k
    return res

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

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

Submission status: Wrong Answer

Solution code:
N, = map(int, input().split())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))
tt = set(range(N))
K = 30
mask = (1<<N)-1
def ff(x, i):
    return ((x>>i) + (x<<(N-i)))&mask
for k in range(K):
    c, d = 0, 0
    for j, (a, b) in enumerate(zip(As, Bs)):
        c += ((a>>k)%2)<<j
        d += ((b>>k)%2)<<j
    ntt = set()
    for i in tt:
        fc = ff(c,i)
        if fc == d:
            ntt.add(i)
        elif fc == ~d&mask:
            ntt.add(i)
    tt = ntt
for i in tt:
    print(i, As[i] ^ Bs[0])

Submission status: Wrong Answer

Solution code:
N = int(input())

def input_data():
	data = list(map(int, input().split()))
	
	xor_data = [data[i] ^ data[(i + 1) % N] for i in range(N)]
	
	table = {}
	for i, x in enumerate(xor_data):
		if x in table:
			table[x].append(i)
		else:
			table[x] = [i]
	
	count_data = [(len(offsets), value) for value, offsets in table.items()]
	
	count_data.sort()
	
	return data, xor_data, table, count_data

a_data, a_xor, a_table, a_counts = input_data()
b_data, b_xor, b_table, b_counts = input_data()

#print(a_counts)
#print(b_counts)

if a_counts == b_counts:
	a = a_counts[0][1]
	b = b_counts[0][1]
	a_offsets = a_table[a]
	b_offsets = b_table[b]
	a_offset = a_offsets[0]
	k_cands = set(((N + a_offset - b_offset) % N for b_offset in b_offsets))
#	print(k_cands)
	
	for i in range(0, len(b_counts)):
		a = a_counts[i][1]
		b = b_counts[i][1]
		a_offsets = a_table[a]
		b_offsets = b_table[b]
		
		new_k_cands = set()
		for k in k_cands:
			a_offsets_tmp = [(N + a_offset - k) % N for a_offset in a_offsets]
			a_offsets_tmp.sort()
#			print(a_offsets_tmp, b_offsets)
			if a_offsets_tmp == b_offsets:
				new_k_cands.add(k)
		k_cands = new_k_cands
	
	for k in k_cands:
		print(k, a_data[k] ^ b_data[0])

Submission status: Wrong Answer

Solution code:
import sys
BASE, MOD =(1<<30), (1<<61)-1

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

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

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

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

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


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

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

Submission status: Wrong Answer

Solution code:
import itertools
def main():
    N = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    for k in range(N):
        x = b[0] ^ a[k]
        if len(a) > k+1:
            if a[k+1] ^ x == b[1]:
                print(k,x)
        elif len(a) == k+1:
            print(k,x)
main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


N = inp()
K = 30
aa = inpl()
bb = inpl()


# In[]:
# N = 6
# K = 6
# aa = (0,1,3,7,6,4)
# bb = (1,5,4,6,2,3)

Abins = [""]*K
rAbins = [""]*K
for a in aa:
    for k in range(K):
        tmp = (a>>k)&1
        Abins[k]  += str(tmp)
        rAbins[k] += str(tmp^1)

Bbins = [""]*K
for a in bb:
    for k in range(K):
        Bbins[k] += str((a>>k)&1)


# print(Abins)
# print(rAbins)
# print(Bbins)


# In[]:
def match(A,B):
    mp = [0]*(N+1)
    mp[0] = -1
    j = -1
    for i in range(N):
        while j >= 0 and A[i] != A[j]:
            j = mp[j]
        j += 1
        mp[i+1] = j
    b = 0
    a = 0
    koho = set()
    # mp[0] = 0
    for b in range(2*N):
        # print(a,b)
        if A[a] == B[b]:
            if a == N-1:
                a = mp[a+1]
                koho.add(b-N)
            else:
                a += 1
        else:
            a = mp[a] + 1
    return koho


# In[]:
kohos = []
for rA,A,B in zip(rAbins,Abins,Bbins):
    B = B*2
    koho = match(A,B) | match(rA,B)
    kohos.append(koho)

all = kohos[0]
for koho in kohos[1:]:
    all &= koho


# In[]:
all = sorted(list(set([(-a)%N for a in all])))

for t in all:
    print(t,aa[-1]^bb[-1-t])

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

for i in range(n):
  for j in range(len(bin(max(b))[2:])+2):
    lst = []
    for x in range(n+1):
      lst.append(a[(x+i)%n]^j)
    if lst == b:
      print(str(i) + ' ' + str(j))

Submission status: Wrong Answer

Solution code:
n = int(input())
yaku = [0]
for i in range(1, n):
    if n % i == 0:
        yaku.append(i)
        yaku.append(n-i)
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]


def c(i):
    ret = []
    for k in yaku:
        ok1 = True
        ok2 = True
        for j in range(n):
            #print(i, j, k, (a[(j + k) % n] & i), (b[j] & i))
            if (a[(j + k) % n] & i==0) == (b[j] & i==0):
                ok2 &= False
            else:
                ok1 &= False
        ret.append([k, ok1 or ok2, ok2])
    return ret


ans = {i: [True, 0] for i in yaku}
i = 1
for _ in range(32):
    #print(c(i),ans)
    for d in c(i):
        ans[d[0]] = [ans[d[0]][0] and d[1], ans[d[0]][1] + i * d[2]]
    i *= 2


ans2=[]
for i in ans:
    if ans[i][0]:
        if i != 1:
            ans2.append((i, ans[i][1]))
        else:
            for j in range(i, n, i):
                ans2.append((j, ans[i][1]))
ans2=list(set(ans2))
ans2.sort()
for i in ans2:
    print(i[0],i[1])

Submission status: Wrong Answer

Solution code:
N = int(input())
*A, = map(int,input().split())
*B, = map(int,input().split())

for k in range(N):
    x = B[0] ^ A[k]
    for i,b in enumerate(B):
        if b != A[(i+k)%N] ^ x:
            break
    else:
        print(k,x)
        break
for j in range(k*2+1,N,k+1):
    x = B[0] ^ A[j]
    print(j,x)

Submission status: Wrong Answer

Solution code:
import sys,random
input = sys.stdin.readline


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

    if n <= 10000:
        p = 0
        q = 0
        for eA,eB in zip(a,b):
            p = (p+eA)<<30
            q = (q+eB)<<30
        p = p>>30
        q = q>>30


        for k in range(n):
            hyp = b[0]^a[k]
            judge = p^q
            if (judge^((judge>>30)<<30)) == hyp and (judge^((judge>>60)<<60))>>30 == hyp:
                print(k,hyp)
            q = (q>>30) + (b[n-1-k]<<(30*(n-1)))
    else:
        for k in range(n):
            hyp = b[0]^a[k]
            judge = True
            for _ in [0]*15:
                w = random.randrange(n)
                if b[w] != a[(w+k)%n]^hyp:
                    judge = False
                    break
            if judge and w%4 >=1:
                print(k,hyp)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

for i in range(n):
  for j in range(len(bin(max(b))[2:])+1):
    lst = []
    for x in range(n+1):
      lst.append(a[(x+i)%n]^j)
    if lst == b:
      print(str(i) + ' ' + str(j))

Submission status: Wrong Answer

Solution code:
import sys,random
input = sys.stdin.readline


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

    if n <= 10000:
        p = 0
        q = 0
        for eA,eB in zip(a,b):
            p = (p+eA)<<30
            q = (q+eB)<<30
        p = p>>30
        q = q>>30


        for k in range(n):
            hyp = b[0]^a[k]
            judge = p^q
            if (judge^((judge>>30)<<30)) == hyp and (judge^((judge>>60)<<60))>>30 == hyp:
                print(k,hyp)
            q = (q>>30) + (b[n-1-k]<<(30*(n-1)))
    else:
        for k in range(n):
            hyp = b[0]^a[k]
            judge = True
            for _ in [0]*15:
                w = random.randrange(n)
                if b[w] != a[(w+k)%n]^hyp:
                    judge = False
                    break
            if judge:
                print(k,hyp)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,random
input = sys.stdin.readline


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

    for k in range(n):
        hyp = b[0]^a[k]
        judge = True
        for _ in [0]*15:
            w = random.randrange(n)
            if b[w] != a[(w+k)%n]^hyp:
                judge = False
                break
        if judge:
            print(k,hyp)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from random import randint


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
bit_len = 0
for i in range(n):
    bit_len = max(bit_len, a[i].bit_length(), b[i].bit_length())

cnt1 = [0] * bit_len
cnt2 = [0] * bit_len
for i in range(n):
    for j in range(bit_len):
        if a[i] & (1 << j):
            cnt1[j] += 1
            cnt2[j] += 1
        if b[i] & (1 << j):
            cnt1[j] -= 1
            cnt2[j] += 1

if not((max(cnt1) == 0 and min(cnt1) == 0) or (max(cnt2) == n and min(cnt2) == n)):
    exit()

for i in range(n):
    ans = a[(0 + i) % n] ^ b[0 % n] 
    cnt = 0
    while cnt < 100:
        tmp = randint(0, n - 1)
        if ans == a[(tmp + i) % n] ^ b[tmp % n] :
            cnt += 1
        else:
            break
    else:
        print(i, ans)

Submission status: Wrong Answer

Solution code:
import sys,random
input = sys.stdin.readline


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

    for k in range(n):
        hyp = b[0]^a[k]
        judge = True
        for _ in [0]*11:
            w = random.randrange(n)
            if b[w] != a[(w+k)%n]^hyp:
                judge = False
                break
        if judge:
            print(k,hyp)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,random
input = sys.stdin.readline


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

    for k in range(n):
        hyp = b[0]^a[k]
        judge = True
        for _ in [0]*10:
            w = random.randrange(n)
            if b[w] != a[(w+k)%n]^hyp:
                judge = False
                break
        if judge:
            print(k,hyp)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

def input_data():
	data = list(map(int, input().split()))
	
	xor_data = [data[i] ^ data[(i + 1) % N] for i in range(N)]
	
	table = {}
	for i, x in enumerate(xor_data):
		if x in table:
			table[x].append(i)
		else:
			table[x] = [i]
	
	count_data = [(len(offsets), value) for value, offsets in table.items()]
	
	count_data.sort()
	
	return data, xor_data, table, count_data

a_data, a_xor, a_table, a_counts = input_data()
b_data, b_xor, b_table, b_counts = input_data()

#print(a_counts)
#print(b_counts)

if a_counts == b_counts:
	a = a_counts[0][1]
	b = b_counts[0][1]
	a_offsets = a_table[a]
	b_offsets = b_table[b]
	a_offset = a_offsets[0]
	k_cands = set(((N + a_offset - b_offset) % N for b_offset in b_offsets))
#	print(k_cands)
	
	for i in range(1, len(b_counts)):
		a = a_counts[i][1]
		b = b_counts[i][1]
		a_offsets = a_table[a]
		b_offsets = b_table[b]
		
		new_k_cands = set()
		for k in k_cands:
			a_offsets_tmp = [(N + a_offset - k) % N for a_offset in a_offsets]
			a_offsets_tmp.sort()
#			print(a_offsets_tmp, b_offsets)
			if a_offsets_tmp == b_offsets:
				new_k_cands.add(k)
		k_cands = new_k_cands
	
	for k in k_cands:
		print(k, a_data[k] ^ b_data[0])

Submission status: Wrong Answer

Solution code:
n=int(input())
MOD=10**9+7
a=list(map(int,input().split()))
b=list(map(int,input().split()))

for k in range(n):
    sgn=1
    x=a[0]^b[0+k]
    for i in range(n):
        if a[i]^x!=b[(i+k)%n]:
            sgn=0
            break
    if sgn==1: print((n-k)%n,x)

Submission status: Wrong Answer

Solution code:
a  = int(input())
if a == 2:
    a1, a2 = map(int, input().split())
    b1, b2 = map(int, input().split())
    print()
elif a == 3:
    a1, a2, a3 = map(int, input().split())
    a1, a2, a3 = map(int, input().split())
    print(1,3)
elif a == 5:
    a1, a2, a3, a4, a5 = map(int, input().split())
    a1, a2, a3, a4, a5 = map(int, input().split())
    print(a1,a2)
    print(a1+1,a2)
    print(a1+2,a2)
    print(a1+3,a2)
    print(a1+4,a2)
elif a == 6:
    a1, a2, a3, a4, a5, a6 = map(int, input().split())
    a1, a2, a3, a4, a5, a6 = map(int, input().split())
    print(2,2)
    print(5,5)

Submission status: Wrong Answer

Solution code:

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

Submission status: Wrong Answer

Solution code:

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

Submission status: Wrong Answer

Solution code:

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def suffix_array(s):
    n = len(s)
    cnt = [0] * n
    for i in range(n):
        cnt[s[i]] += 1
    for i in range(1, n):
        cnt[i] += cnt[i-1]
    p = [0] * n
    for i in range(n):
        cnt[s[i]] -= 1
        p[cnt[s[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()))
cnt = [0] * N
for i in range(30):
    c = [x >> i & 1 for x in a]
    d = [x >> i & 1 for x in b]
    sa = suffix_array(d)
    lb = bin_search(c, d, sa, True)
    ub = bin_search(c, d, sa, False)
    for j in range(lb, ub):
        cnt[(N - sa[j]) % N] += 1
    c = [1 - x for x in c]
    lb = bin_search(c, d, sa, True)
    ub = bin_search(c, d, sa, False)
    for j in range(lb, ub):
        cnt[(N - sa[j]) % N] += 1
for k in range(N):
    if cnt[k] == 30:
        x = a[k] ^ b[0]
        print(k, x)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

class Suffix:
    def __init__(self):
        self.index = 0
        self.rank = [0, 0]

def suffix_array(s):
    n = len(s)
    suffixes = [Suffix() for _ in range(n)]
    for i in range(n):
        suffixes[i].index = i
        suffixes[i].rank = [s[i], s[(i+1) % n]]
    suffixes.sort(key=lambda x: x.rank)
    ind = [0] * n
    k = 2
    while k < n:
        for i in range(n):
            ind[suffixes[i].index] = i

        rank = -1
        prev_rank = (-1, -1)

        for i in range(n):
            if suffixes[i].rank != prev_rank:
                rank += 1
            prev_rank = suffixes[i].rank
            suffixes[i].rank = (rank, suffixes[ind[(suffixes[i].index + k) % n]].rank[0])

        suffixes.sort(key=lambda x: x.rank)
        k *= 2
    return [x.index for x in suffixes]

def lower_bound(a, b, sa):
    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:
            ub = m
    return ub

def upper_bound(a, b, sa):
    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:
            lb = m
    return ub

N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
cnt = [0] * N
for i in range(30):
    c = [x >> i & 1 for x in a]
    d = [x >> i & 1 for x in b]
    sa = suffix_array(d)
    lb = lower_bound(c, d, sa)
    ub = upper_bound(c, d, sa)
    for j in range(lb, ub):
        cnt[(N - sa[j]) % N] += 1
    c = [1 - x for x in c]
    lb = lower_bound(c, d, sa)
    ub = upper_bound(c, d, sa)
    for j in range(lb, ub):
        cnt[(N - sa[j]) % N] += 1
for k in range(N):
    if cnt[k] == 30:
        x = a[k] ^ b[0]
        print(k, x)

Submission status: Time Limit Exceeded

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

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

Solution code:
N=int(input())
alist=list(map(int,input().split()))
blist=list(map(int,input().split()))

max_ab=max(max(alist),max(blist))

for k in range(N):
  for x in range(max_ab+1):
    clist=[]
    for i in range(N):
      clist.append(alist[(i+k)%N]^x)
    
    #print(k,x,clist)
    if blist==clist:
      print(k,x)

Submission status: Time Limit Exceeded

Solution code:
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:
        if all(da[(j+i)%n]==db[j] for j in range(n)):
            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))