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-----
3
0 2 1
1 2 3

-----Sample Output-----
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.

Difficulty: interview

Starter code:

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

A.append(A[0])
B.append(B[0])

AX=[]
BX=[]
for i in range(N):
    AX.append(A[i]^A[i+1])
    BX.append(B[i]^B[i+1])

AX+=AX+[AX[0]]

# Rolling Hashで。

p=1<<30
mod=(1<<62)+1 # Hashがぶつからない, pと互いに素な数を適当に指定

A_TABLE=[0] # Rolling Hashのテーブル. 最初は0
B_TABLE=[0] # Rolling Hashのテーブル. 最初は0

for i in range(len(AX)):
    A_TABLE.append((p*A_TABLE[-1]%mod+AX[i])%mod) # テーブルを埋める

for i in range(len(BX)):
    B_TABLE.append((p*B_TABLE[-1]%mod+BX[i])%mod) # テーブルを埋める

def hash(i,j): # [i,j)のハッシュ値を求める
    return (A_TABLE[j]-A_TABLE[i]*pow(p,j-i,mod))%mod

BH=B_TABLE[-1]
ANS=[]
for i in range(N):
    if hash(i,i+N)==BH:
        ANS.append((i,A[i]^B[0]))

for a in ANS:
    print(*a)

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]
    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=np.roll(A,-kouho[i])
        if all(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])

#!/usr/bin/env python3
import sys
input = sys.stdin.readline

class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base = 1009
        self.mod = (1 << 61) - 1
        self.hash = [0] * (self.length + 1)
        self.pow = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash[i+1] = (self.hash[i] + s[i]) * self.base % self.mod
            self.pow[i+1] = self.pow[i] * self.base % self.mod

    def get(self, l, r):
        t = self.hash[r] - self.hash[l] * self.pow[r-l] % self.mod
        t = (t + self.mod) % self.mod
        return t

n = int(input())
a = [int(item) for item in input().split()]
b = [int(item) for item in input().split()]
a = a + a

diffa = []
diffb = []
for i in range(1, len(a)):
    diffa.append(a[i] ^ a[i-1])
for i in range(1, len(b)):
    diffb.append(b[i] ^ b[i-1])

RHa = RollingHash(diffa)
RHb = RollingHash(diffb)
query = RHb.get(0, n-1)
ans = []
for i in range(n):
    val = RHa.get(i, i+n-1)
    if val == query:
        ans.append((i, a[i] ^ b[0]))
ans.sort()
for k, x in ans:
    print(k, x)

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

# 左の箱（パターンにあたる）と右の箱（対象）が連動して動く
# 文字が同じ限り右に広げて、lcpを記録しながら左に縮めていく感じ
# 縮められなくなったら、topを右の箱の左端にして、左の箱を0までずらす
# 箱ができていない（幅が0）のときは、右の箱を1つ右に

def ZAlgorithm(aa):
    target = aa
    # s = input()
    len_t = len(target)
    lcp = [-1] * len_t
    top = 1  # 右の箱において、左の箱の0に対応する点
    left = 0  # 左の箱の左端(本当はここでので宣言は不要だけど理解の為)
    right = 0  # 左の箱の右端
    lcp[0] = 0
    while top < len_t:
        # 箱を右に広げていく
        while top + right < len_t and target[right] == target[top + right]:
            right += 1
        # 右の箱左端のlcpを記録
        lcp[top] = right
        left = 1
        # 箱の幅が0だったらtopを動かして、このターン終了
        if right == 0:
            top += 1
            continue
        # lcpを記録しながら箱を左に縮めていく（最初の条件重要）
        while left + lcp[left] < right and left < right:
            lcp[top + left] = lcp[left]
            left += 1
        # topを右の箱の左端にして、左の箱を0まで戻す
        top += left
        right -= left
        left = 0  # これも本当は不要
    return lcp

def main():
    # 「aを左にシフト」＝「bを右にシフト」
    # 左にシフトは面倒なのでbを右に動かす
    # 動かした(下記は2つシフトしたとき)結果
    #  a0  a1  a2  a3  a4
    # xor xor xor xor xor
    #  x   x   x   x   x
    #  =   =   =   =   =
    #  b3  b4  b0  b1  b2
    # と、なっていればよい。ここで、xorをただの足し算に置き換えて考える
    #  a0  a1  a2  a3  a4
    #  +   +   +   +   +
    #  x   x   x   x   x
    #  =   =   =   =   =
    #  b3  b4  b0  b1  b2
    # 具体例で
    #  4   6   3   7   2
    #  +   +   +   +   +
    #  1   1   1   1   1
    #  =   =   =   =   =
    #  5   7   4   8   3
    # このとき、aの増減とbの増減は一致する
    # aの増減・・・末尾から(+2) 4 (+2) 6 (-3) 3 (+4) 7 (-5) 2
    # bの増減・・・末尾から(+2) 5 (+2) 7 (-3) 4 (+4) 8 (-5) 3
    # これはxorでも同様のことがいえる
    # よって、a,bそれぞれの隣接xorのリストを作る
    # aを2つ並べて(ループするから)、bを右にシフトしながら一致する位置を探す
    # 一致する位置を探すのはZ-Algorithmを使った
    # シフト量が分かれば、対応する1組のa,bからxも分かる
    # らしいが、こんなの思いつかんわ!!

    inf = pow(2, 31)
    n = II()
    aa = LI()
    bb = LI()
    ax = [aa[i - 1] ^ aa[i] for i in range(n)]
    bx = [bb[i - 1] ^ bb[i] for i in range(n)]
    # print(ax)
    # print(bx)
    ll = ZAlgorithm(bx + [inf] + ax + ax[:-1])
    # lcp・・・length common prefixみたいな?
    for shift, lcp in enumerate(ll[n + 1:]):
        if lcp == n: print(shift, aa[shift] ^ bb[0])

main()


# coding: utf-8

def main():

	# N = 0
	# a = []
	# b = []
	# with open("C:/Users/admin/Downloads/random_05") as f:
	# 	N = int(f.readline())
	# 	a = [int(x) for x in f.readline().split()]
	# 	b = [int(x) for x in f.readline().split()]

	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)

	ans = kmp.full_search()
	for k in ans:
		if k == len(a):
			break
		print(str(k) + " " + str(a[0 + k] ^ b[0]))

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

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

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

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

		return res

	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

def __starting_point():
	main()
__starting_point()

import sys
input=sys.stdin.readline

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

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

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 = []

    m = 2147483647
    g = 1000000007
    s = 0
    for c in ccc:
        s = (s * g + c) % m
    t = 0
    for d in ddd:
        t = (t * g + d) % m
    u = pow(g, n, m) - 1
    for i in range(n):
        if s == t:
            ans.append((i, aaa[i] ^ bbb[0]))
        s = (s * g - ccc[i] * u) % m
    ans.sort()
    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)))


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

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


main()

import sys
input = sys.stdin.readline

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

def z_algo(S):
    N = len(S)
    A = [0]*N
    A[0] = N
    i, j = 1, 0
    while i < N:
        while i+j < N and S[j] == S[i+j]:
            j += 1
        A[i] = j
        if not j:
            i += 1
            continue
        k = 1
        while i+k < N and k+A[k] < j:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A  

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

import sys
input = sys.stdin.readline


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

h = 10**11+7
b = 10**7+7

H = [1]
for _ in range(N):
    H.append((H[-1]*b)%h)

allSum = 0
for i in range(N):
    allSum = (allSum + H[i]) % h

ok = [True]*N
ans = [0]*N

C = []
D = []
for i in range(N):
    C.append(A[i-1]^A[i])
    D.append(B[i-1]^B[i])


HashA = 0
for i, a in enumerate(C):
    HashA = (HashA + a*H[i]%h) % h

HashB = 0
for i, a in enumerate(D):
    HashB = (HashB + a*H[i]%h) % h

ans = []
for k in range(N):
    if HashA == HashB:
        ans.append(k)
    HashB = (HashB * b) % h
    HashB = (HashB + (1-H[N])*D[-k-1] % h) % h

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

import sys
BASE, MOD1, MOD2 = (1<<30), (1<<61)-1, (1<<31)-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])
	return
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])

rh1_x, rh1_y = RollingHash(x, BASE, MOD1), RollingHash(y, BASE, MOD1)
rh2_x, rh2_y = RollingHash(x, BASE, MOD2), RollingHash(y, BASE, MOD2)
for k in range(n):
	if rh1_y.concatenate(n-k, n, 0, n-k) == rh1_x.get(0, n) and rh2_y.concatenate(n-k, n, 0, n-k) == rh2_x.get(0, n):
		print(k, a[0]^b[(n-k)%n])

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

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


C = [0] * (2 * N - 1)
D = [0] * N
for i in range(2 * N - 1):
    C[i] = A[i % N] ^ A[(i + 1) % N]
    D[i % N] = B[i % N] ^ B[(i + 1) % N]

class KMP:

    def __init__(self, W):
        self.W = W
        self.L = len(W)
        self.T = self._build(W)

    def _build(self, W):
        T = [0] * self.L
        T[0] = -1
        T[1] = 0
        i = 2
        j = 0

        while i < self.L:
            if W[i - 1] == W[j]:
                T[i] = j + 1
                i += 1
                j += 1
            elif j > 0:
                j = T[j]
            else:
                T[i] = 0
                i += 1

        return T

    def search(self, S):
        m = 0
        i = 0
        L = len(S)
        while m + i < L:
            # print(m, i)
            if self.W[i] == S[m + i]:
                i += 1
                if i == self.L:
                    i -= 1
                    ret = m
                    m = m + i - self.T[i]
                    i = self.T[i]
                    yield ret
            else:
                m = m + i - self.T[i]
                if i > 0:
                    i = self.T[i]

# def ok(x, i):
#     for j in range(N):
#         if A[(j + i) % N] ^ B[j] != x:
#             return False
#     return True
#
#
# for i in range(N):
#     x = A[i] ^ B[0]
#     if ok(x, i):
#         print(i, x)

kmp = KMP(D)
for x in kmp.search(C):
    xor = A[x] ^ B[0]
    print(x, xor)

import sys
input = sys.stdin.readline


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

h = 10**11+7
b = 10**7+7

H = [1]
for _ in range(N):
    H.append((H[-1]*b)%h)

C = []
D = []
for i in range(N):
    C.append(A[i-1]^A[i])
    D.append(B[i-1]^B[i])


HashA = 0
for i, a in enumerate(C):
    HashA = (HashA + a*H[i]%h) % h

HashB = 0
for i, a in enumerate(D):
    HashB = (HashB + a*H[i]%h) % h

ans = []
for k in range(N):
    if HashA == HashB:
        ans.append(k)
    HashB = (HashB * b) % h
    HashB = (HashB + (1-H[N])*D[-k-1] % h) % h

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

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
f = [0]*n
g = [0]*n
for i in range(n):
  f[i] = a[i] ^ a[(i+1)%n]
  g[i] = b[i] ^ b[(i+1)%n]

def KMP(S, W):
    ls, lw = len(S), len(W)
    m, i = 0, 0
    T = _KMP_table(W)
    res = list()
    while m + i < ls:
        if W[i] == S[m + i]:
            i += 1
            if i == lw:
                res.append(m)
                m += i - T[i]
                if i > 0:
                    i = T[i]
        else:
            m += i - T[i]
            if i > 0:
                i = T[i]
    return res


def _KMP_table(W):
    W += ['$']
    lw = len(W)
    T = [0] * lw
    T[0] = -1
    i, j = 2, 0
    while i < lw:
        if W[i - 1] == W[j]:
            T[i] = j + 1
            i += 1
            j += 1
        elif j > 0:
            j = T[j]
        else:
            T[i] = 0
            i += 1
    return T
res = KMP(f*2, g)
for x in res:
  if x < n:
    print(x, a[x]^b[0])

def xor_next(values):
    result = [0] * len(values)
    for i in range(len(values)):
        result[i] = values[i] ^ values[(i+1) % len(values)]
    return result


def make_mp_table(values):
    result = [-1] * (len(values) + 1)
    j = -1
    for i in range(len(values)):
        while j != -1 and values[j] != values[i]:
            j = result[j]
        j += 1
        result[i+1] = j
    return result


def mp_find(target, pattern, table):
    result = []
    j = 0
    for i in range(len(target)):
        while(j != -1 and pattern[j] != target[i]):
            j = table[j]
        j += 1
        if j == len(pattern):
            result.append(i-(j-1))
            j = table[j]
    return result


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

    xa = xor_next(a)
    xb = xor_next(b)
    mp_t = make_mp_table(xa)
    xb += xb
    res = mp_find(xb, xa, mp_t)
    res.sort(reverse=True)
    for i in range(len(res)):
        k = n-res[i]
        if(k >= n):
            continue
        x = a[k] ^ b[0]
        print((str(k) + ' ' + str(x)))


main()


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

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

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

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

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

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

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

A.append(A[0])
B.append(B[0])

AX=[]
BX=[]
for i in range(N):
    AX.append(A[i]^A[i+1])
    BX.append(B[i]^B[i+1])

AX+=AX[:-1]

# MP法


LEN=len(BX)
MP=[-1]*(LEN+1) #「接頭辞と接尾辞が最大何文字一致しているか」を記録する配列
NOW=-1 # 何文字一致しているか.

for i in range(LEN):
    while NOW>=0 and BX[i]!=BX[NOW]: # 一致していなかったら0から数え直すのではなく, MP[NOW]から数える.
        NOW=MP[NOW]
    NOW+=1
    MP[i+1]=NOW

LEN2=len(AX)

MP_SEARCH=[0]*(LEN2) # その文字までで何個一致しているかを調べる. LEN文字一致したらSが検出できたということ.
NOW=0
for i in range(LEN2):
    while NOW>=0 and AX[i]!=BX[NOW]:
        NOW=MP[NOW]
    NOW+=1
    MP_SEARCH[i]=NOW

    if NOW==LEN: # LEN文字一致したら, MP[LEN]から数える.
        NOW=MP[NOW]
        
for i in range(LEN2):
    if MP_SEARCH[i]==LEN:
        print(i-LEN+1,A[i-LEN+1]^B[0])

def z_algo(S):
    # Z-algoirhm  O(n)
    # Z[i] := S と S[i:] で prefix が何文字一致しているか
    # 検証: https://atcoder.jp/contests/arc055/submissions/14179788
    i, j, n = 1, 0, len(S)
    Z = [0] * n
    Z[0] = n
    while i < n:
        while i+j < n and S[j] == S[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        Z[i] = j
        d = 1
        while i+d < n and d+Z[d] < j:
            Z[i+d] = Z[d]
            d += 1
        i += d
        j -= d
    return Z


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


class KMP:
    def __init__(self, P):
        self.P = P
        self.N = len(P)
        self.T = [0] * (self.N + 1)
        self._compile()

    def _compile(self):
        j = 0
        self.T[0] = -1
        for i in range(1, self.N):
            self.T[i] = j
            j += 1 if self.P[i] == self.P[j] else -j
        self.T[self.N] = j

    def search(self, S):
        NS = len(S)
        i = m = 0
        A = []
        while m + i < NS:
            if self.P[i] == S[m + i]:
                i += 1
                if i != self.N:
                    continue
                A.append(m)
            m += i - self.T[i]
            i = max(0, self.T[i])
        return A

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = [A[i]^A[(i+1)%N] for i in range(N)]
D = [B[i]^B[(i+1)%N] for i in range(N)]
C = C + C[:-1]
K = KMP(D).search(C)
for k in K:
    print(k, A[k]^B[0])

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

# print(c)
# print(d)

# テーブル作成
table = [0]
k = 0
for i in range(1, num+1):
    table.append(k)
    if i == num:
        continue
    
    if d[i] == d[k]:
        k += 1
    else:
        k = 0

# print(table)

i = 0 # 探索される文字列の位置
j = 0 # 探索する文字列の位置
k = 0 # kの初期値
while k < num:
    
    while True:
        # print(i, j, k)
        if c[i] == d[j]:
            if j == num - 1:
                print(k, a[k] ^ b[0])
                i += 1
                j = table[num]
                k = i - j
                break
            
            i += 1
            j += 1
        elif j != 0:
            j -= 1
        else:    
            i += 1
            j = table[j]
            break
    
    k = i - j