Consider an array, $\mbox{A}$, of $n$ integers ($A=a_0,a_1,...,a_{n-1}$). 
We take all consecutive subsequences of integers from the array that satisfy the following:
$\{a_i,a_{i+1},\ldots,a_{j-1},aj\},\text{where}\ 0\leq i\leq j<n$ 

For example, if $n=3$ our subsequences will be:

$\boldsymbol{a_0}$
$a_1$    
$a_2$    
$a_{0},a_{1}$
$a_{1},a_{2}$
$a_{0},a_{1},a_{2}$ 

For each subsequence, we apply the bitwise XOR ($\oplus$) operation on all the integers and record the resultant value. Since there are $n\times\frac{(n+1)}{2}$ subsequences, this will result in $n\times\frac{(n+1)}{2}$ numbers.   

Given array $\mbox{A}$, find the XOR sum of every subsequence of $\mbox{A}$ and determine the frequency at which each number occurs. Then print the number and its respective frequency as two space-separated values on a single line.  

Input Format

The first line contains an integer, $n$, denoting the size of the array. 

Each line $\boldsymbol{i}$ of the $n$ subsequent lines contains a single integer describing element $a_i$.

Constraints

$1\leq n\leq10^5$
$1\leq a_i<2^{16}$

Output Format

Print $2$ space-separated integers on a single line. The first integer should be the number having the highest frequency, and the second integer should be the number's frequency (i.e., the number of times it appeared). If there are multiple numbers having maximal frequency, choose the smallest one.

Sample Input 0
4
2
1
1
3

Sample Output 0
1 3

Explanation 0

Let's find the XOR sum for all consecutive subsequences. We'll refer to the frequency of some number $\boldsymbol{x}$ as $f(x)$, and keep a running sum for each frequency:  

$2=2$, frequencies: $f(2)=1$
$1=1$, frequencies: $f(1)=1$ and $f(2)=1$
$1=1$, frequencies: $f(1)=2$ and $f(2)=1$
$3=3$, frequencies: $f(1)=2$, $f(2)=1$, and $f(3)=1$
$2\oplus1=3$, frequencies: $f(1)=2$, $f(2)=1$, and $f(3)=2$
$1\oplus1=0$, frequencies: $f(0)=1$, $f(1)=2$, $f(2)=1$, and $f(3)=2$
$1\oplus3=2$, frequencies: $f(0)=1$, $f(1)=2$, $f(2)=2$, and $f(3)=2$
$2\oplus1\oplus1=2$, frequencies: $f(0)=1$, $f(1)=2$, $f(2)=3$, and $f(3)=2$  
$1\oplus1\oplus3=3$, frequencies: $f(0)=1$, $f(1)=2$, $f(2)=3$, and $f(3)=3$   
$2\oplus1\oplus1\oplus3=1$, frequencies: $f(0)=1$, $f(1)=3$, $f(2)=3$, and $f(3)=3$     

Our maximal frequency is $3$, and the integers $1$, $2$, and $3$ all have this frequency. Because more than one integer has this frequency, we choose the smallest one, which is $1$. We then print the respective smallest number having the maximal frequency and the maximal frequency as a single line of space-separated values.

Source: hackerrank | Difficulty: HARD
Tags: Bit manipulation


Solutions:
from sys import stderr
from itertools import accumulate
from operator import xor
MAXNUM = 1 << 16

def main():
	n = int(input())
	a = [int(input()) for _ in range(n)]
	c = [0] * MAXNUM
	for elt in accumulate(a, xor):
		c[elt] += 1
	c[0] += 1
	conv = xorfft((i * i for i in xorfft(c)))
	conv[0] = 2 * MAXNUM * sum((i * (i - 1) // 2 for i in c))
	ans = max(((v, -i) for (i, v) in enumerate(conv)))
	print(-ans[1], ans[0] // (2 * MAXNUM))

def xorfft(a):
	a = list(a)
	la = len(a)
	assert la & la - 1 == 0
	k = 1
	while k < la:
		for i in range(0, la, 2 * k):
			for j in range(i, i + k):
				(x, y) = (a[j], a[j + k])
				(a[j], a[j + k]) = (x + y, x - y)
		k <<= 1
	return a
main()


from sys import stderr
from itertools import accumulate
from operator import xor
MAXNUM = 1 << 16

def main():
	n = int(input())
	a = [int(input()) for _ in range(n)]
	c = [0] * MAXNUM
	for elt in accumulate(a, xor):
		c[elt] += 1
	c[0] += 1
	conv = xorfft((i * i for i in xorfft(c)))
	conv[0] = 2 * MAXNUM * sum((i * (i - 1) // 2 for i in c))
	ans = max(((v, -i) for (i, v) in enumerate(conv)))
	print(-ans[1], ans[0] // (2 * MAXNUM))

def xorfft(a):
	a = list(a)
	la = len(a)
	assert la & la - 1 == 0
	k = 1
	while k < la:
		for i in range(0, la, 2 * k):
			for j in range(i, i + k):
				(x, y) = (a[j], a[j + k])
				(a[j], a[j + k]) = (x + y, x - y)
		k <<= 1
	return a
main()


def fwht(a):
	h = 1
	while h < len(a):
		for i in range(0, len(a), h << 1):
			for j in range(i, i + h):
				k = j + h
				x = a[j]
				y = a[k]
				a[j] = x + y
				a[k] = x - y
		h <<= 1
n = int(input())
bits = 16
a = [0] * (1 << bits)
a[0] = 1
xor = 0
for i in range(n):
	xor ^= int(input())
	a[xor] += 1
fwht(a)
for i in range(len(a)):
	a[i] *= a[i]
fwht(a)
bits += 1
best = 1
high = a[1] >> bits
for i in range(2, len(a)):
	x = a[i] >> bits
	if x > high:
		high = x
		best = i
print(best, high)


def fwht(a):
	h = 1
	while h < len(a):
		for i in range(0, len(a), h << 1):
			for j in range(i, i + h):
				k = j + h
				x = a[j]
				y = a[k]
				a[j] = x + y
				a[k] = x - y
		h <<= 1
n = int(input())
bits = 16
a = [0] * (1 << bits)
a[0] = 1
xor = 0
for i in range(n):
	xor ^= int(input())
	a[xor] += 1
fwht(a)
for i in range(len(a)):
	a[i] *= a[i]
fwht(a)
bits += 1
best = 1
high = a[1] >> bits
for i in range(2, len(a)):
	x = a[i] >> bits
	if x > high:
		high = x
		best = i
print(best, high)


from sys import stderr
from itertools import accumulate
from operator import xor
MAXNUM = 1 << 16

def main():
	n = int(input())
	a = [int(input()) for _ in range(n)]
	c = [0] * MAXNUM
	for elt in accumulate(a, xor):
		c[elt] += 1
	c[0] += 1
	conv = xorfft((i * i for i in xorfft(c)))
	conv[0] = 2 * MAXNUM * sum((i * (i - 1) // 2 for i in c))
	ans = max(((v, -i) for (i, v) in enumerate(conv)))
	print(-ans[1], ans[0] // (2 * MAXNUM))

def xorfft(a):
	a = list(a)
	la = len(a)
	assert la & la - 1 == 0
	k = 1
	while k < la:
		for i in range(0, la, 2 * k):
			for j in range(i, i + k):
				(x, y) = (a[j], a[j + k])
				(a[j], a[j + k]) = (x + y, x - y)
		k <<= 1
	return a
main()


from sys import stderr
from itertools import accumulate
from operator import xor
MAXNUM = 1 << 16

def main():
	n = int(input())
	a = [int(input()) for _ in range(n)]
	c = [0] * MAXNUM
	for elt in accumulate(a, xor):
		c[elt] += 1
	c[0] += 1
	conv = xorfft((i * i for i in xorfft(c)))
	conv[0] = 2 * MAXNUM * sum((i * (i - 1) // 2 for i in c))
	ans = max(((v, -i) for (i, v) in enumerate(conv)))
	print(-ans[1], ans[0] // (2 * MAXNUM))

def xorfft(a):
	a = list(a)
	la = len(a)
	assert la & la - 1 == 0
	k = 1
	while k < la:
		for i in range(0, la, 2 * k):
			for j in range(i, i + k):
				(x, y) = (a[j], a[j + k])
				(a[j], a[j + k]) = (x + y, x - y)
		k <<= 1
	return a
main()


import math
import os
import random
import re
import sys
from sys import stderr
from itertools import accumulate
from operator import xor
MAXNUM = 1 << 16

def main():
	n = int(input())
	a = [int(input()) for _ in range(n)]
	c = [0] * MAXNUM
	for elt in accumulate(a, xor):
		c[elt] += 1
	c[0] += 1
	conv = xorfft((i * i for i in xorfft(c)))
	conv[0] = 2 * MAXNUM * sum((i * (i - 1) // 2 for i in c))
	ans = max(((v, -i) for (i, v) in enumerate(conv)))
	print(-ans[1], ans[0] // (2 * MAXNUM))

def xorfft(a):
	a = list(a)
	la = len(a)
	assert la & la - 1 == 0
	k = 1
	while k < la:
		for i in range(0, la, 2 * k):
			for j in range(i, i + k):
				(x, y) = (a[j], a[j + k])
				(a[j], a[j + k]) = (x + y, x - y)
		k <<= 1
	return a
main()


from sys import stderr
from itertools import accumulate
from operator import xor
MAXNUM = 1 << 16

def main():
	n = int(input())
	a = [int(input()) for _ in range(n)]
	c = [0] * MAXNUM
	for elt in accumulate(a, xor):
		c[elt] += 1
	c[0] += 1
	conv = xorfft((i * i for i in xorfft(c)))
	conv[0] = 2 * MAXNUM * sum((i * (i - 1) // 2 for i in c))
	ans = max(((v, -i) for (i, v) in enumerate(conv)))
	print(-ans[1], ans[0] // (2 * MAXNUM))

def xorfft(a):
	a = list(a)
	la = len(a)
	assert la & la - 1 == 0
	k = 1
	while k < la:
		for i in range(0, la, 2 * k):
			for j in range(i, i + k):
				(x, y) = (a[j], a[j + k])
				(a[j], a[j + k]) = (x + y, x - y)
		k <<= 1
	return a
main()


M = 1 << 16

def FWHT(V, inv=False):
	H = 1
	while H < M:
		for L in range(0, M, 2 * H):
			for I in range(H):
				X = V[L + I]
				Y = V[L + H + I]
				V[L + H + I] = X - Y
				V[L + I] = X + Y
				if inv:
					V[L + H + I] >>= 1
					V[L + I] >>= 1
		H <<= 1
N = int(input())
A = []
for _ in range(N):
	A.append(int(input()))
B = [0]
for E in A:
	B.append(B[-1] ^ E)
CNT = [0] * (1 << 16)
for E in B:
	CNT[E] += 1
FWHT(CNT)
for i in range(len(CNT)):
	CNT[i] *= CNT[i]
FWHT(CNT, True)
Y = 0
X = -1
for i in range(1, len(CNT)):
	if CNT[i] > Y:
		X = i
		Y = CNT[i]
print(X, Y // 2)


from sys import stderr
from itertools import accumulate
from operator import xor
MAXNUM = 1 << 16

def main():
	n = int(input())
	a = [int(input()) for _ in range(n)]
	c = [0] * MAXNUM
	for elt in accumulate(a, xor):
		c[elt] += 1
	c[0] += 1
	conv = xorfft((i * i for i in xorfft(c)))
	conv[0] = 2 * MAXNUM * sum((i * (i - 1) // 2 for i in c))
	ans = max(((v, -i) for (i, v) in enumerate(conv)))
	print(-ans[1], ans[0] // (2 * MAXNUM))

def xorfft(a):
	a = list(a)
	la = len(a)
	assert la & la - 1 == 0
	k = 1
	while k < la:
		for i in range(0, la, 2 * k):
			for j in range(i, i + k):
				(x, y) = (a[j], a[j + k])
				(a[j], a[j + k]) = (x + y, x - y)
		k <<= 1
	return a
main()


from sys import stderr
from itertools import accumulate
from operator import xor
MAXNUM = 1 << 16

def main():
	n = int(input())
	a = [int(input()) for _ in range(n)]
	c = [0] * MAXNUM
	for elt in accumulate(a, xor):
		c[elt] += 1
	c[0] += 1
	conv = xorfft((i * i for i in xorfft(c)))
	conv[0] = 2 * MAXNUM * sum((i * (i - 1) // 2 for i in c))
	ans = max(((v, -i) for (i, v) in enumerate(conv)))
	print(-ans[1], ans[0] // (2 * MAXNUM))

def xorfft(a):
	a = list(a)
	la = len(a)
	assert la & la - 1 == 0
	k = 1
	while k < la:
		for i in range(0, la, 2 * k):
			for j in range(i, i + k):
				(x, y) = (a[j], a[j + k])
				(a[j], a[j + k]) = (x + y, x - y)
		k <<= 1
	return a
main()


from sys import stderr
from itertools import accumulate
from operator import xor
MAXNUM = 1 << 16

def main():
	n = int(input())
	a = [int(input()) for _ in range(n)]
	c = [0] * MAXNUM
	for elt in accumulate(a, xor):
		c[elt] += 1
	c[0] += 1
	conv = xorfft((i * i for i in xorfft(c)))
	conv[0] = 2 * MAXNUM * sum((i * (i - 1) // 2 for i in c))
	ans = max(((v, -i) for (i, v) in enumerate(conv)))
	print(-ans[1], ans[0] // (2 * MAXNUM))

def xorfft(a):
	a = list(a)
	la = len(a)
	assert la & la - 1 == 0
	k = 1
	while k < la:
		for i in range(0, la, 2 * k):
			for j in range(i, i + k):
				(x, y) = (a[j], a[j + k])
				(a[j], a[j + k]) = (x + y, x - y)
		k <<= 1
	return a
main()


import math
import os
import random
import re
import sys
from sys import stderr
from itertools import accumulate
from operator import xor
MAXNUM = 1 << 16

def main():
	n = int(input())
	a = [int(input()) for _ in range(n)]
	c = [0] * MAXNUM
	for elt in accumulate(a, xor):
		c[elt] += 1
	c[0] += 1
	conv = xorfft((i * i for i in xorfft(c)))
	conv[0] = 2 * MAXNUM * sum((i * (i - 1) // 2 for i in c))
	ans = max(((v, -i) for (i, v) in enumerate(conv)))
	print(-ans[1], ans[0] // (2 * MAXNUM))

def xorfft(a):
	a = list(a)
	la = len(a)
	assert la & la - 1 == 0
	k = 1
	while k < la:
		for i in range(0, la, 2 * k):
			for j in range(i, i + k):
				(x, y) = (a[j], a[j + k])
				(a[j], a[j + k]) = (x + y, x - y)
		k <<= 1
	return a
main()


import math
import os
import random
import re
import sys
from sys import stderr
from itertools import accumulate
from operator import xor
MAXNUM = 1 << 16

def main():
	n = int(input())
	a = [int(input()) for _ in range(n)]
	c = [0] * MAXNUM
	for elt in accumulate(a, xor):
		c[elt] += 1
	c[0] += 1
	conv = xorfft((i * i for i in xorfft(c)))
	conv[0] = 2 * MAXNUM * sum((i * (i - 1) // 2 for i in c))
	ans = max(((v, -i) for (i, v) in enumerate(conv)))
	print(-ans[1], ans[0] // (2 * MAXNUM))

def xorfft(a):
	a = list(a)
	la = len(a)
	assert la & la - 1 == 0
	k = 1
	while k < la:
		for i in range(0, la, 2 * k):
			for j in range(i, i + k):
				(x, y) = (a[j], a[j + k])
				(a[j], a[j + k]) = (x + y, x - y)
		k <<= 1
	return a
main()


from sys import stderr
from itertools import accumulate
from operator import xor
MAXNUM = 1 << 16

def main():
	n = int(input())
	a = [int(input()) for _ in range(n)]
	c = [0] * MAXNUM
	for elt in accumulate(a, xor):
		c[elt] += 1
	c[0] += 1
	conv = xorfft((i * i for i in xorfft(c)))
	conv[0] = 2 * MAXNUM * sum((i * (i - 1) // 2 for i in c))
	ans = max(((v, -i) for (i, v) in enumerate(conv)))
	print(-ans[1], ans[0] // (2 * MAXNUM))

def xorfft(a):
	a = list(a)
	la = len(a)
	assert la & la - 1 == 0
	k = 1
	while k < la:
		for i in range(0, la, 2 * k):
			for j in range(i, i + k):
				(x, y) = (a[j], a[j + k])
				(a[j], a[j + k]) = (x + y, x - y)
		k <<= 1
	return a
main()


from sys import stderr
from itertools import accumulate
from operator import xor
MAXNUM = 1 << 16

def main():
	n = int(input())
	a = [int(input()) for _ in range(n)]
	c = [0] * MAXNUM
	for elt in accumulate(a, xor):
		c[elt] += 1
	c[0] += 1
	conv = xorfft((i * i for i in xorfft(c)))
	conv[0] = 2 * MAXNUM * sum((i * (i - 1) // 2 for i in c))
	ans = max(((v, -i) for (i, v) in enumerate(conv)))
	print(-ans[1], ans[0] // (2 * MAXNUM))

def xorfft(a):
	a = list(a)
	la = len(a)
	assert la & la - 1 == 0
	k = 1
	while k < la:
		for i in range(0, la, 2 * k):
			for j in range(i, i + k):
				(x, y) = (a[j], a[j + k])
				(a[j], a[j + k]) = (x + y, x - y)
		k <<= 1
	return a
main()


from sys import stderr
from itertools import accumulate
from operator import xor
MAXNUM = 1 << 16

def main():
	n = int(input())
	a = [int(input()) for _ in range(n)]
	c = [0] * MAXNUM
	for elt in accumulate(a, xor):
		c[elt] += 1
	c[0] += 1
	conv = xorfft((i * i for i in xorfft(c)))
	conv[0] = 2 * MAXNUM * sum((i * (i - 1) // 2 for i in c))
	ans = max(((v, -i) for (i, v) in enumerate(conv)))
	print(-ans[1], ans[0] // (2 * MAXNUM))

def xorfft(a):
	a = list(a)
	la = len(a)
	assert la & la - 1 == 0
	k = 1
	while k < la:
		for i in range(0, la, 2 * k):
			for j in range(i, i + k):
				(x, y) = (a[j], a[j + k])
				(a[j], a[j + k]) = (x + y, x - y)
		k <<= 1
	return a
main()


from sys import stderr
from itertools import accumulate
from operator import xor
MAXNUM = 1 << 16

def main():
	n = int(input())
	a = [int(input()) for _ in range(n)]
	c = [0] * MAXNUM
	for elt in accumulate(a, xor):
		c[elt] += 1
	c[0] += 1
	conv = xorfft((i * i for i in xorfft(c)))
	conv[0] = 2 * MAXNUM * sum((i * (i - 1) // 2 for i in c))
	ans = max(((v, -i) for (i, v) in enumerate(conv)))
	print(-ans[1], ans[0] // (2 * MAXNUM))

def xorfft(a):
	a = list(a)
	la = len(a)
	assert la & la - 1 == 0
	k = 1
	while k < la:
		for i in range(0, la, 2 * k):
			for j in range(i, i + k):
				(x, y) = (a[j], a[j + k])
				(a[j], a[j + k]) = (x + y, x - y)
		k <<= 1
	return a
main()


from sys import stderr
from itertools import accumulate
from operator import xor
MAXNUM = 1 << 16

def main():
	n = int(input())
	a = [int(input()) for _ in range(n)]
	c = [0] * MAXNUM
	for elt in accumulate(a, xor):
		c[elt] += 1
	c[0] += 1
	conv = xorfft((i * i for i in xorfft(c)))
	conv[0] = 2 * MAXNUM * sum((i * (i - 1) // 2 for i in c))
	ans = max(((v, -i) for (i, v) in enumerate(conv)))
	print(-ans[1], ans[0] // (2 * MAXNUM))

def xorfft(a):
	a = list(a)
	la = len(a)
	assert la & la - 1 == 0
	k = 1
	while k < la:
		for i in range(0, la, 2 * k):
			for j in range(i, i + k):
				(x, y) = (a[j], a[j + k])
				(a[j], a[j + k]) = (x + y, x - y)
		k <<= 1
	return a
main()


from sys import stderr
from itertools import accumulate
from operator import xor
MAXNUM = 1 << 16

def main():
	n = int(input())
	a = [int(input()) for _ in range(n)]
	c = [0] * MAXNUM
	for elt in accumulate(a, xor):
		c[elt] += 1
	c[0] += 1
	conv = xorfft((i * i for i in xorfft(c)))
	conv[0] = 2 * MAXNUM * sum((i * (i - 1) // 2 for i in c))
	ans = max(((v, -i) for (i, v) in enumerate(conv)))
	print(-ans[1], ans[0] // (2 * MAXNUM))

def xorfft(a):
	a = list(a)
	la = len(a)
	assert la & la - 1 == 0
	k = 1
	while k < la:
		for i in range(0, la, 2 * k):
			for j in range(i, i + k):
				(x, y) = (a[j], a[j + k])
				(a[j], a[j + k]) = (x + y, x - y)
		k <<= 1
	return a
main()


from sys import stderr
from itertools import accumulate
from operator import xor
MAXNUM = 1 << 16

def main():
	n = int(input())
	a = [int(input()) for _ in range(n)]
	c = [0] * MAXNUM
	for elt in accumulate(a, xor):
		c[elt] += 1
	c[0] += 1
	conv = xorfft((i * i for i in xorfft(c)))
	conv[0] = 2 * MAXNUM * sum((i * (i - 1) // 2 for i in c))
	ans = max(((v, -i) for (i, v) in enumerate(conv)))
	print(-ans[1], ans[0] // (2 * MAXNUM))

def xorfft(a):
	a = list(a)
	la = len(a)
	assert la & la - 1 == 0
	k = 1
	while k < la:
		for i in range(0, la, 2 * k):
			for j in range(i, i + k):
				(x, y) = (a[j], a[j + k])
				(a[j], a[j + k]) = (x + y, x - y)
		k <<= 1
	return a
main()


from sys import stderr
from itertools import accumulate
from operator import xor
MAXNUM = 1 << 16

def main():
	n = int(input())
	a = [int(input()) for _ in range(n)]
	c = [0] * MAXNUM
	for elt in accumulate(a, xor):
		c[elt] += 1
	c[0] += 1
	conv = xorfft((i * i for i in xorfft(c)))
	conv[0] = 2 * MAXNUM * sum((i * (i - 1) // 2 for i in c))
	ans = max(((v, -i) for (i, v) in enumerate(conv)))
	print(-ans[1], ans[0] // (2 * MAXNUM))

def xorfft(a):
	a = list(a)
	la = len(a)
	assert la & la - 1 == 0
	k = 1
	while k < la:
		for i in range(0, la, 2 * k):
			for j in range(i, i + k):
				(x, y) = (a[j], a[j + k])
				(a[j], a[j + k]) = (x + y, x - y)
		k <<= 1
	return a
main()


from sys import stderr
from itertools import accumulate
from operator import xor
MAXNUM = 1 << 16

def main():
	v = int(input())
	a = [int(input()) for _ in range(v)]
	c = [0] * MAXNUM
	for elt in accumulate(a, xor):
		c[elt] += 1
	c[0] += 1
	conv = xorfft((i * i for i in xorfft(c)))
	conv[0] = 2 * MAXNUM * sum((i * (i - 1) // 2 for i in c))
	ans = max(((v, -i) for (i, v) in enumerate(conv)))
	print(-ans[1], ans[0] // (2 * MAXNUM))

def xorfft(a):
	a = list(a)
	la = len(a)
	assert la & la - 1 == 0
	k = 1
	while k < la:
		for i in range(0, la, 2 * k):
			for j in range(i, i + k):
				(x, y) = (a[j], a[j + k])
				(a[j], a[j + k]) = (x + y, x - y)
		k <<= 1
	return a
main()


from sys import stderr
from itertools import accumulate
from operator import xor
MAXNUM = 1 << 16

def main():
	n = int(input())
	a = [int(input()) for _ in range(n)]
	c = [0] * MAXNUM
	for elt in accumulate(a, xor):
		c[elt] += 1
	c[0] += 1
	conv = xorfft((i * i for i in xorfft(c)))
	conv[0] = 2 * MAXNUM * sum((i * (i - 1) // 2 for i in c))
	ans = max(((v, -i) for (i, v) in enumerate(conv)))
	print(-ans[1], ans[0] // (2 * MAXNUM))

def xorfft(a):
	a = list(a)
	la = len(a)
	assert la & la - 1 == 0
	k = 1
	while k < la:
		for i in range(0, la, 2 * k):
			for j in range(i, i + k):
				(x, y) = (a[j], a[j + k])
				(a[j], a[j + k]) = (x + y, x - y)
		k <<= 1
	return a
main()


import enum
from sys import stderr
from itertools import accumulate
from operator import xor
MAXNUM = 1 << 16

def main():
	n = int(input())
	a = [int(input()) for _ in range(n)]
	c = [0] * MAXNUM
	for elt in accumulate(a, xor):
		c[elt] += 1
	c[0] += 1
	conv = xorfft((i * i for i in xorfft(c)))
	conv[0] = 2 * MAXNUM * sum((i * (i - 1) // 2 for i in c))
	ans = max(((v, -i) for (i, v) in enumerate(conv)))
	print(-ans[1], ans[0] // (2 * MAXNUM))

def xorfft(a):
	a = list(a)
	la = len(a)
	assert la & la - 1 == 0
	k = 1
	while k < la:
		for i in range(0, la, 2 * k):
			for j in range(i, i + k):
				(x, y) = (a[j], a[j + k])
				(a[j], a[j + k]) = (x + y, x - y)
		k <<= 1
	return a
main()