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:
import numpy as np
n = int(input())
a = np.array(input().split(),dtype=int)
b = np.array(input().split(),dtype=int)

c = np.zeros(n)
d = np.zeros(n)
k = []
for i in range(n):
    c[i] = a[i]^a[(i+1)%n]
    d[i] = b[i]^b[(i+1)%n]
for i in range(n):
    if c[i] == d[0]:
        flag = True
        for j in range(n):
            if not c[(i+j)%n] == d[j]:
                flag = False
                break
        if flag:
            k.append(i)

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

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)

c = np.zeros(n)
d = np.zeros(n)
k = []
for i in range(n):
    c[i] = a[i]^a[(i+1)%n]
    d[i] = b[i]^b[(i+1)%n]
for i in range(n):
    flag = True
    for j in range(n):
        if not c[(i+j)%n] == d[j]:
            flag = False
            break
    if flag:
        k.append(i)

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

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)

for i in range(n):
    flag = True
    x = a[i]^b[0]
    for j in range(n):
        if not a[(i+j)%n]^x == b[j]:
            flag = False
            break
    if flag:
        print(i,x)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python


def read():
    raw_input()
    a = map(int, raw_input().split())
    b = map(int, raw_input().split())
    return a, b


def work((a, b)):
    nNum = len(a)
    P = 1 << 30

    baseP = 0
    for i in range(nNum):
        baseP = baseP * P + 1

    bBaseP = 0
    for i in range(nNum):
        bBaseP = bBaseP * P + b[i]

    rollingHash = 0
    for i in range(nNum):
        rollingHash = rollingHash * P + a[i]

    pPowNNum = P ** (nNum - 1)

    for shift in range(nNum):
        v = a[shift] ^ b[0]
        if (baseP * v) ^ bBaseP == rollingHash:
            print shift, v

        rollingHash = rollingHash - a[shift] * pPowNNum
        rollingHash = rollingHash * P + a[shift]


if __name__ == "__main__":
    work(read())

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions
from functools import reduce

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

ans = []

for i in range(n):
  c = a[(0+i)%n] ^ b[0]
  j = 1
  while j < n:
    if c == a[(j+i)%n] ^ b[j]:
      j += 1
    else:
      break
  else:
    ans.append([str(i), str(c)])
for i in range(len(ans)):
  print(" ".join(ans[i]))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A = []
B = []
ans = []
for i in range(N):
    A.append(a[i]^a[(i+1)%N])
    B.append(b[i]^b[(i+1)%N])
A += A    
from collections import defaultdict
d = defaultdict(list)
for i in range(N):
    d[B[i]].append(i)
i = 0
ans = []
while i < N:
    ok = True
    for j in range(N):
        if B[N-j-1] != A[N-j-1+i]:
            if d[A[N-j-1]] == []:
                i += N
                ok = False
                break
            else:
                i += N - d[A[N-j-1+i]][-1] - 1
                ok = False
                break
    if ok:
        ans.append((i,a[i]^b[0]))
        if len(d[A[N-1+i]]) == 1:
            i += N
        else:
            i += N - d[A[N-1+i]][-2] - 1
for x in ans:
    print(*x)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A = []
B = []
ans = []
for i in range(N):
    A.append(a[i]^a[(i+1)%N])
    B.append(b[i]^b[(i+1)%N])
A += A    
from collections import defaultdict
d = defaultdict(int)
for i in range(N):
    d[B[i]] = i+1
i = 0
ans = []
while i < N:
    ok = True
    for j in range(N):
        if B[N-j-1] != A[N-j-1+i]:
            if d[B[N-j-1]] == 0:
                i += N
                ok = False
                break
            else:
                i += N - d[B[N-j-1]] + 1
                ok = False
                break
    if ok:
        ans.append((i,a[i]^b[0]))
        i += 1
for x in ans:
    print(*x)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
for i in range(n):
    x = a[i%n] ^ b[0]
    for j in range(1, n):
        if a[(i+j)%n] ^ b[j] != x:
            break
    else:
        print(i, x)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A = []
B = []
ans = []
for i in range(N):
    A.append(a[i]^a[(i+1)%N])
    B.append(b[i]^b[(i+1)%N])
for k in range(N):
    C = A[k:]+A[:k]
    if B == C:
        ans.append((k,a[k]^b[0]))
for x in ans:
    print(*x)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = []
for k in range(N):
    x = a[k]^b[0]
    ok = True
    for i in range(N):
        if not b[i]^x == a[(k+i)%N]:
            ok = False
    if ok:
        ans.append((k,x))
for y in ans:
    print(*y)

Submission status: Time Limit Exceeded

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

# process/output
# A[i+k+]^A[i+k+1]=B[i]^B[i+1]となるkを求める
AX = [A[i]^A[i-1] for i in range(N)]
BX = [B[i]^B[i-1] for i in range(N)]

ans = []
for k in range(N):
    AX2 = AX[k:N]
    AX2.extend(AX[0:k])
    if AX2 == BX:
        # kに対応するxを求める
        x = A[k]^B[0]
        print(k, x)

Submission status: Time Limit Exceeded

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

# process/output
# A[i+k+]^A[i+k+1]=B[i]^B[i+1]となるkを求める
AX = [A[i]^A[i+1] for i in range(N-1)]
BX = [B[i]^B[i+1] for i in range(N-1)]
AX.append(A[N-1]^A[0])
BX.append(B[N-1]^B[0])

ans = []
for k in range(N):
    i = 0
    while i < N:
        j = i+k
        if j >= N:
            j -= N

        if not BX[i] == AX[j]:
            break
        i += 1
    
    if i == N:
        # kに対応するxを求める
        x = A[k]^B[0]
        print(k, x)

Submission status: Time Limit Exceeded

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

# process
# A[i+k+]^A[i+k+1]=B[i]^B[i+1]となるkを求める
AX = [0]*N
BX = [0]*N
for i in range(N-1):
    AX[i] = A[i]^A[i+1]
    BX[i] = B[i]^B[i+1]
AX[N-1] = (A[N-1]^A[0])
BX[N-1] = (B[N-1]^B[0])

ans = []
for k in range(N):
    i = 0
    while i < N:
        j = i+k
        if j >= N:
            j -= N

        if not BX[i] == AX[j]:
            break
        i += 1
    
    if i == N:
        # kに対応するxを求める
        x = A[k]^B[0]
        ans.append((k, x))

# output
for k, x in ans:
    print("{} {}".format(k,x))

Submission status: Time Limit Exceeded

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

N = int(input())
aa = np.array(list(map(int, input().split())))
bb = np.array(list(map(int, input().split())))

for i in range(N):
	cc = np.concatenate([aa[i:], aa[:i]], 0)
	cc = cc^bb
	if(np.all(cc==cc[0])):
		print(i, cc[0])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
# kmp.py
import time

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

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

    if j == len(pattern):
        return i - j
    else:
        return None


n = int(input())
a = [int(_) for _ in input().split()]
b = [int(_) for _ in input().split()]
c = ''
for i in range(n - 1):
    c += str(a[i] ^ a[i+1])
c += str(a[-1] ^ a[0])
d = ''
for i in range(n - 1):
    d += str(b[i] ^ b[i+1])
d += str(b[-1] ^ b[0])
d = d + d[:-1]

idx_list = []
i = 0
idx = kmp_search(d, c, i)
while idx is not None:
    idx_list.append(idx)
    i = idx + 1
    idx = kmp_search(d, c, i)

ans = []
for i in range(len(idx_list)):
    if idx_list[i] == 0:
        k = 0
    else:
        k = n - idx_list[i]
    x = a[k] ^ b[0]
    ans.append((k, x))

ans = sorted(ans)
for i in range(len(ans)):
    print(ans[i][0], ans[i][1])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(_) for _ in input().split()]
b = [int(_) for _ in input().split()]
ans = []
for k in range(n):
    a_dash = a[k % n] ^ b[0]
    flag = 0
    for i in range(1, n):
        if a[(i+k) % n] ^ b[i] != a_dash:
            flag = 1
            break
    if flag == 0:
        ans.append((k, a_dash))
ans = sorted(ans)
for i in range(len(ans)):
    print(' '.join([str(ans[i][0]), str(ans[i][1])]))

Submission status: Time Limit Exceeded

Solution code:
class RollingHash:
    def __init__(self, s: list, base: int = 1007, mod: int = 10**9 + 7):
        self.s = s
        self.n = len(s)
        self.base = base
        self.mod = mod

        # preprocess
        self.h_cum = [0] * (self.n + 1)  # h_cum[i] = (hash of s[:i])
        self.b_pow = [1] * (self.n + 1)  # b_pow[i] = base ** i
        # for i in range(self.n):
        #     self.h_cum[i + 1] = (self.h_cum[i] * base + s[i]) % mod
        #     self.b_pow[i + 1] = (self.b_pow[i] * base) % mod
        for i, si in enumerate(s):
            self.h_cum[i + 1] = (self.h_cum[i] * base + si % mod) % mod
            self.b_pow[i + 1] = (self.b_pow[i] * base) % mod

    def get_hash(self, l: int, r: int) -> int:
        # get hash value of the substring s[l:r]
        hash_val = self.h_cum[r] - self.h_cum[l] * self.b_pow[r - l] % self.mod
        if hash_val < 0:
            hash_val += self.mod
        return hash_val


class RollingHashMulti:
    def __init__(self,
                 s: list,
                 base_list: list = [1007, 2009],
                 mod_list: list = [10**9 + 7, 10**9 + 9]):
        self.n = len(base_list)
        self.base_list = base_list
        self.mod_list = mod_list
        self.rh_list = [
            RollingHash(s, base_list[i], mod_list[i]) for i in range(self.n)
        ]

    def get_hash(self, l: int, r: int) -> tuple:
        return tuple(self.rh_list[i].get_hash(l, r) for i in range(self.n))


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

# a_xor = [a[i % n] ^ a[(i + 1) % n] for i in range(n * 2)]
# b_xor = [b[i % n] ^ b[(i + 1) % n] for i in range(n * 2)]
a_xor = [a[i % n] ^ a[(i + 1) % n] for i in range(n)] * 2
b_xor = [b[i % n] ^ b[(i + 1) % n] for i in range(n)] * 2

a_xor_rh = RollingHashMulti(a_xor)
b_xor_rh = RollingHashMulti(b_xor)

b_hash = b_xor_rh.get_hash(0, n)
for k in range(n):
    if a_xor_rh.get_hash(k, k + n) == b_hash:
        x = a[k] ^ b[0]
        print(k, x)

Submission status: Time Limit Exceeded

Solution code:
class RollingHash:
    def __init__(self, s: list, base: int = 1007, mod: int = 10**9 + 7):
        self.s = s
        self.n = len(s)
        self.base = base
        self.mod = mod

        # preprocess
        self.h_cum = [0] * (self.n + 1)  # h_cum[i] = (hash of s[:i])
        self.b_pow = [1] * (self.n + 1)  # b_pow[i] = base ** i
        # for i in range(self.n):
        #     self.h_cum[i + 1] = (self.h_cum[i] * base + s[i]) % mod
        #     self.b_pow[i + 1] = (self.b_pow[i] * base) % mod
        for i, si in enumerate(s):
            self.h_cum[i + 1] = (self.h_cum[i] * base + si) % mod
            self.b_pow[i + 1] = (self.b_pow[i] * base) % mod

    def get_hash(self, l: int, r: int) -> int:
        # get hash value of the substring s[l:r]
        hash_val = self.h_cum[r] - self.h_cum[l] * self.b_pow[r - l] % self.mod
        if hash_val < 0:
            hash_val += self.mod
        return hash_val


class RollingHashMulti:
    def __init__(self,
                 s: list,
                 base_list: list = [1007, 2009],
                 mod_list: list = [10**9 + 7, 10**9 + 9]):
        self.n = len(base_list)
        self.base_list = base_list
        self.mod_list = mod_list
        self.rh_list = [
            RollingHash(s, base_list[i], mod_list[i]) for i in range(self.n)
        ]

    def get_hash(self, l: int, r: int) -> tuple:
        return tuple(self.rh_list[i].get_hash(l, r) for i in range(self.n))


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

# a_xor = [a[i % n] ^ a[(i + 1) % n] for i in range(n * 2)]
# b_xor = [b[i % n] ^ b[(i + 1) % n] for i in range(n * 2)]
a_xor = [a[i % n] ^ a[(i + 1) % n] for i in range(n)] * 2
b_xor = [b[i % n] ^ b[(i + 1) % n] for i in range(n)] * 2

a_xor_rh = RollingHashMulti(a_xor)
b_xor_rh = RollingHashMulti(b_xor)

b_hash = b_xor_rh.get_hash(0, n)
for k in range(n):
    if a_xor_rh.get_hash(k, k + n) == b_hash:
        x = a[k] ^ b[0]
        print(k, x)

Submission status: Time Limit Exceeded

Solution code:
class RollingHash:
    def __init__(self, s: list, base: int = 1007, mod: int = 10**9 + 7):
        self.s = s
        self.n = len(s)
        self.base = base
        self.mod = mod

        # preprocess
        self.h_cum = [0] * (self.n + 1)  # h_cum[i] = (hash of s[:i])
        self.b_pow = [1] * (self.n + 1)  # b_pow[i] = base ** i
        for i in range(self.n):
            self.h_cum[i + 1] = (self.h_cum[i] * base + s[i]) % mod
            self.b_pow[i + 1] = (self.b_pow[i] * base) % mod

    def get_hash(self, l: int, r: int) -> int:
        # get hash value of the substring s[l:r]
        hash_val = self.h_cum[r] - self.h_cum[l] * self.b_pow[r - l] % self.mod
        if hash_val < 0:
            hash_val += self.mod
        return hash_val


class RollingHashMulti:
    def __init__(self,
                 s: list,
                 base_list: list = [1007, 2009],
                 mod_list: list = [10**9 + 7, 10**9 + 9]):
        self.n = len(base_list)
        self.base_list = base_list
        self.mod_list = mod_list
        self.rh_list = [
            RollingHash(s, base_list[i], mod_list[i]) for i in range(self.n)
        ]

    def get_hash(self, l: int, r: int) -> tuple:
        return tuple(self.rh_list[i].get_hash(l, r) for i in range(self.n))


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

# a_xor = [a[i % n] ^ a[(i + 1) % n] for i in range(n * 2)]
# b_xor = [b[i % n] ^ b[(i + 1) % n] for i in range(n * 2)]
a_xor = [a[i % n] ^ a[(i + 1) % n] for i in range(n)] * 2
b_xor = [b[i % n] ^ b[(i + 1) % n] for i in range(n)] * 2

a_xor_rh = RollingHashMulti(a_xor)
b_xor_rh = RollingHashMulti(b_xor)

b_hash = b_xor_rh.get_hash(0, n)
for k in range(n):
    if a_xor_rh.get_hash(k, k + n) == b_hash:
        x = a[k] ^ b[0]
        print(k, x)

Submission status: Time Limit Exceeded

Solution code:
class RollingHash:
    def __init__(self, s: list, base: int = 1007, mod: int = 10**9 + 7):
        self.s = s
        self.n = len(s)
        self.base = base
        self.mod = mod

        # preprocess
        self.h_cum = [0] * (self.n + 1)  # h_cum[i] = (hash of s[:i])
        self.b_pow = [1] * (self.n + 1)  # b_pow[i] = base ** i
        for i in range(self.n):
            self.h_cum[i + 1] = (self.h_cum[i] * base + s[i]) % mod
            self.b_pow[i + 1] = (self.b_pow[i] * base) % mod

    def get_hash(self, l: int, r: int) -> int:
        # get hash value of the substring s[l:r]
        hash_val = self.h_cum[r] - self.h_cum[l] * self.b_pow[r - l] % self.mod
        if hash_val < 0:
            hash_val += self.mod
        return hash_val


class RollingHashMulti:
    def __init__(self,
                 s: list,
                 base_list: list = [1007, 2009],
                 mod_list: list = [10**9 + 7, 10**9 + 9]):
        self.n = len(base_list)
        self.base_list = base_list
        self.mod_list = mod_list
        self.rh_list = [
            RollingHash(s, base_list[i], mod_list[i]) for i in range(self.n)
        ]

    def get_hash(self, l: int, r: int) -> tuple:
        return tuple(self.rh_list[i].get_hash(l, r) for i in range(self.n))


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

# a_xor = [a[i % n] ^ a[(i + 1) % n] for i in range(n * 2)]
# b_xor = [b[i % n] ^ b[(i + 1) % n] for i in range(n * 2)]
a_xor = [a[i % n] ^ a[(i + 1) % n] for i in range(n)] * 2
b_xor = [b[i % n] ^ b[(i + 1) % n] for i in range(n)] * 2

a_xor_rh = RollingHashMulti(a_xor)
b_xor_rh = RollingHashMulti(b_xor)

b_hash = b_xor_rh.get_hash(0, n)
for k in range(n):
    if a_xor_rh.get_hash(k, k + n) == b_hash:
        x = a[k] ^ b[0]
        print(k, x)

Submission status: Time Limit Exceeded

Solution code:
class RollingHash:
    def __init__(self, s: list, base: int = 1007, mod: int = 10**9 + 7):
        self.s = s
        self.n = len(s)
        self.base = base
        self.mod = mod

        # preprocess
        self.h_cum = [0] * (self.n + 1)  # h_cum[i] = (hash of s[:i])
        self.b_pow = [1] * (self.n + 1)  # b_pow[i] = base ** i
        for i in range(self.n):
            self.h_cum[i + 1] = (self.h_cum[i] * base + s[i]) % mod
            self.b_pow[i + 1] = (self.b_pow[i] * base) % mod

    def get_hash(self, l: int, r: int) -> int:
        # get hash value of the substring s[l:r]
        hash_val = self.h_cum[r] - self.h_cum[l] * self.b_pow[r - l] % self.mod
        if hash_val < 0:
            hash_val += self.mod
        return hash_val


class RollingHashMulti:
    def __init__(self,
                 s: list,
                 base_list: list = [1007, 2009],
                 mod_list: list = [10**9 + 7, 10**9 + 9]):
        self.n = len(base_list)
        self.base_list = base_list
        self.mod_list = mod_list
        self.rh_list = [
            RollingHash(s, base_list[i], mod_list[i]) for i in range(self.n)
        ]

    def get_hash(self, l: int, r: int) -> tuple:
        return tuple(self.rh_list[i].get_hash(l, r) for i in range(self.n))


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

a_xor = [a[i % n] ^ a[(i + 1) % n] for i in range(n * 2)]
b_xor = [b[i % n] ^ b[(i + 1) % n] for i in range(n * 2)]

a_xor_rh = RollingHashMulti(a_xor)
b_xor_rh = RollingHashMulti(b_xor)

b_hash = b_xor_rh.get_hash(0, n)
for k in range(n):
    if a_xor_rh.get_hash(k, k + n) == b_hash:
        x = a[k] ^ b[0]
        print(k, x)

Submission status: Time Limit Exceeded

Solution code:
class RollingHash:
    def __init__(self, s: list, base: int = 1007, mod: int = 10**9 + 7):
        self.s = s
        self.n = len(s)
        self.base = base
        self.mod = mod

        # preprocess
        self.h_cum = [0] * (self.n + 1)  # h_cum[i] = (hash of s[:i])
        self.b_pow = [1] * (self.n + 1)  # b_pow[i] = base ** i
        for i in range(self.n):
            self.h_cum[i + 1] = (self.h_cum[i] * base + s[i]) % mod
            self.b_pow[i + 1] = (self.b_pow[i] * base) % mod

    def get_hash(self, l: int, r: int) -> int:
        # get hash value of the substring s[l:r]
        hash_val = self.h_cum[r] - self.h_cum[l] * self.b_pow[r - l] % self.mod
        if hash_val < 0:
            hash_val += self.mod
        return hash_val


class RollingHashMulti:
    def __init__(self,
                 s: list,
                 base_list: list = [1007, 2009],
                 mod_list: list = [10**9 + 7, 10**9 + 9]):
        self.n = len(base_list)
        self.base_list = base_list
        self.mod_list = mod_list
        self.rh_list = [
            RollingHash(s, base_list[i], mod_list[i]) for i in range(self.n)
        ]

    def get_hash(self, l: int, r: int) -> tuple:
        return tuple(self.rh_list[i].get_hash(l, r) for i in range(self.n))


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

a_xor = [a[i % n] ^ a[(i + 1) % n] for i in range(n * 2)]
b_xor = [b[i % n] ^ b[(i + 1) % n] for i in range(n * 2)]

a_xor_rh = RollingHashMulti(a_xor)
b_xor_rh = RollingHashMulti(b_xor)

for k in range(n):
    if a_xor_rh.get_hash(k, k + n) == b_xor_rh.get_hash(0, n):
        x = a[k] ^ b[0]
        print(k, x)

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = []
d = []

for i in range(num):
    c.append(a[i] ^ a[(i+1)%num])
    d.append(b[i] ^ b[(i+1)%num])
    
c += c

for k in range(num):
    if d == c[k:num+k]:
        print(k, a[k] ^ b[0])

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = []
d = []

for i in range(num):
    c.append(a[i] ^ a[(i+1)%num])
    d.append(b[i] ^ b[(i+1)%num])

for k in range(num):
    c_rotated_k = []
    for i in range(num):
        c_rotated_k.append(c[(i+k)%num])
    if c_rotated_k == d:
        print(k, a[k] ^ b[0])

Submission status: Time Limit Exceeded

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

for k in range(num):
    a_rotate_k = []
    for i in range(num):
        a_rotate_k.append(a[(i+k) % num])
        
    for i in range(1, num):
        if a_rotate_k[i] ^ b[i] != a_rotate_k[0] ^ b[0]:
            break
    else:
        print(k, a_rotate_k[0] ^ b[0])

Submission status: Time Limit Exceeded

Solution code:
# F - Xor Shift

N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
assert len(a) == N and len(b) == N

# 直前の要素とのxor (循環)
a_xor = [a[i] ^ a[(i + 1) % N] for i in range(N)]
# 直前の要素とのxor (先頭を除く)
b_xor = [b[i] ^ b[i + 1] for i in range(N - 1)]

# (k,x)が解 ⇔ a_xor[k:]がb_xorと一致, x = b[0] XOR a[k]

# a_xorのsuffix-arrayを構築

def make_suffix_array(s):
    """Manber & Myers法で配列sのsuffix-arrayを構築して返す."""
    N = len(s)

    # rank[i] = s[i]
    rank = s[0:N]
    spare = [0] * N  # 作業用配列

    # sa[i] = i
    sa = [i for i in range(N)]
    # s[i]の大小で整列
    sa.sort(key=lambda i: s[i])

    # h = 1, 2, 4, 8, ...
    h = 1
    while h < N:
        sa.sort(key=lambda i: (rank[i], rank[(i + h) % N]))

        # rankの再構築
        cmp = lambda i, j: \
            (rank[(i + h) % N] < rank[(j + h) % N]) if rank[i] == rank[j] \
            else (rank[i] < rank[j])
        spare[sa[0]] = 0
        for j in range(1, N):
            spare[sa[j]] = spare[sa[j - 1]] \
                         + (1 if cmp(sa[j - 1], sa[j]) else 0)
        rank, spare = spare, rank
        h <<= 1
    return sa

sa = make_suffix_array(a_xor)

# a_xor[k:k+N-1] == b_xor となるkを探す

def bin_search(low, high, less_than_target):
    """low: 探索範囲の左端, high: 探索範囲の右端+1,
       less_than_target(i)が偽になる最小のiを返す."""
    while low < high:
        mid = low + (high - low) // 2
        if less_than_target(mid):
            low = mid + 1
        else:
            high = mid
    return low

def axor_less_than_bxor(i):
    """a_xor[sa[i]:sa[i]+N-1] < b_xor か?"""
    for j in range(N - 1):
        if a_xor[(sa[i] + j) % N] != b_xor[j]:
            return a_xor[(sa[i] + j) % N] < b_xor[j]
    return False
def axor_eq_bxor(i):
    """a_xor[sa[i]:sa[i]+N-1] == b_xor か?"""
    return all(a_xor[(sa[i] + j) % N] == b_xor[j] for j in range(N - 1))

i = bin_search(0, N, axor_less_than_bxor)
while i < N and axor_eq_bxor(i):
    k = sa[i]
    print(k, b[0] ^ a[k])
    i += 1

Submission status: Time Limit Exceeded

Solution code:
def p_f():
    N = int(input())
    *A, = map(int, input().split())
    *B, = map(int, input().split())
    max_bit = len(bin(max(A + B))) - 2
    bit_a = []
    bit_b = []
    for i in range(max_bit):
        num = 0
        for a in A:
            num <<= 1
            num += (a >> i) & 1
        bit_a.append(num)
        num = 0
        for b in B:
            num <<= 1
            num += (b >> i) & 1
        bit_b.append(num)

    ans = [0] * N
    n_bit = 0
    for a, b in zip(bit_a, bit_b):
        b = (b << N) + b
        getter = (1 << N) - 1
        for i in range(N):
            if a == ((b >> i) & getter):
                pass
            elif a == ((b >> i) & getter ^ getter):
                ans[i] += 1 << n_bit if ans[i] != -1 else 0
            else:
                ans[i] = -1
        n_bit += 1

    for i, v in enumerate(ans):
        if v != -1:
            print(i, v)


if __name__ == '__main__':
    p_f()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
B = 10 ** 8 + 7


def Hash(l, n, k_, x_):
    h = 0
    if x_ != 0:
        for i in range(n):
            h = h * B - (l[(i + k_) % n] ^ x) * (B ** (n - 1)) + (l[(i + k_) % n] ^ x)
    else:
        for i in range(n):
            h = h * B - (l[(i + k_) % n]) * (B ** (n - 1)) + (l[(i + k_) % n])
    return h


def R_Rollhash(m):
    mm = m % B
    m = mm + mm * (B ** (N - 1))
    return m


bh = Hash(b, N, 0, 0)
for k in range(N):
    x = a[k] ^ b[0]
    ah = Hash(a, N, k, x)
    if ah == bh:
        print(k, x)
    R_Rollhash(bh)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def create_table(pattern):
    table = [0 for _ in range(len(pattern))]
    j = 0
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
        else:
            table[i] = j
            j = 0
    return table

def kmp_search(string, pattern):
    table = create_table(pattern)
    i = j = 0
    ret=[]
    while i < len(string): #and j < len(pattern):
        if string[i] == pattern[j]:
            i += 1
            j += 1
        elif j == 0:
            i += 1
        else:
            j = table[j]
        if j == len(pattern):
            ret.append(i - j)
            j=table[j-1]
    return ret
#print(kmp_search(list('abcabc'),list('abc')))
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
a.append(a[0])
b.append(b[0])
a2=[]
b2=[]
for i in range(n):
    a2.append(a[i]^a[i+1])
    b2.append(b[i]^b[i+1])
aa=a2+a2
aa.pop(-1)
k=kmp_search(aa,b2)
ans=[]
for i in k:
    if i<n:
      ans.append([i,a[i]^b[0]])
for i in ans:
    print(*i)

Submission status: Time Limit Exceeded

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

def kmp_search(string, pattern):
    table = create_table(pattern)
    i = j = 0
    ret=[]
    while i < len(string): #and j < len(pattern):
        if string[i] == pattern[j]:
            i += 1
            j += 1
        elif j == 0:
            i += 1
        else:
            j = table[j]
        if j == len(pattern):
            ret.append(i - j)
            j=table[j-1]
    return ret
#print(kmp_search(list('abcabc'),list('abc')))
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
a.append(a[0])
b.append(b[0])
a2=[]
b2=[]
for i in range(n):
    a2.append(a[i]^a[i+1])
    b2.append(b[i]^b[i+1])
aa=a2+a2
aa.pop(-1)
k=kmp_search(aa,b2)
ans=[]
for i in k:
    if i<n:
      ans.append([i,a[i]^b[0]])
for i in ans:
    print(*i)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
B = 10**8 + 7


def Make_HashList(l, n):
    hash_list = []
    hash = 0
    for i in range(n):
        hash = hash * B + l[i]
    hash_list.append(hash)
    for j in range(n - 1):
        hash = hash // B + (l[N - 1 -j] * (B ** (n - 1)))
        hash_list.append(hash)
    return hash_list


bhl = Make_HashList(b, N)
for k in range(N):
    x = a[k] ^ b[0]
    ah = 0
    if a[k] ^ x == b[0]:
        for j in range(N):
            ah = ah * B + (a[j] ^ x)
        if ah == bhl[k]:
            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()))
B = 10**8 + 7


def Make_HashList(l, n):
    hash_list = []
    hash = 0
    for i in range(n):
        hash = hash * B + l[i]
    hash_list.append(hash)
    for j in range(n - 1):
        hash = hash // B + (l[N - 1 -j] * (B ** (n - 1)))
        hash_list.append(hash)
    return hash_list


bhl = Make_HashList(b, N)
for k in range(N):
    x = a[k] ^ b[0]
    ah = 0
    for j in range(N):
        ah = ah * B + (a[j] ^ x)
    if ah == bhl[k]:
        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()))
for k in range(N):
    x = a[k % N] ^ b[0]
    for i in range(N):
        if x != a[(k+i) % N] ^ b[i]:
            break
    else:
        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()))
for k in range(N):
    x = A[0] ^ B[0]
    if all(a ^ b == x for a, b in zip(A[1:], B[1:])):
        print(k, x)
    A[:] = A[1:] + [A[0]]

Submission status: Time Limit Exceeded

Solution code:
def left_shift(arr, n):
    return arr[n:] + arr[:n]

def adash(alist, k, x):
    alist_ = left_shift(alist, k)
    return [ a ^ x for a in alist_]

n = int(input())
alist = list(map(int, input().split()))
blist = list(map(int, input().split()))

amax = max(blist)
memo = []
for k in range(0, n):
    for x in range(0, n+1):
        alist_dash = adash(alist, k, x)
        if alist_dash == blist:
            memo.append([k, x])

for m in memo:
    print('{} {}'.format(m[0], m[1]))