Read problems statements in [Mandarin Chinese], [Russian], [Vietnamese] and [Bengali] as well. 

Given an array A of N non-negative integers, you can choose any non-negative integer X and replace every element A_{i} with (A_{i}\oplus X) Here, \oplus denotes the [bitwise XOR operation].

Using the above operation exactly once, your goal is to minimize the bitwise OR of the new array. In other words, find X such that (A_{1}\oplus X)\lor \cdots \lor (A_{N} \oplus X) is minimized, where \lor denotes the [bitwise OR operation].

Find the value of X and the minimum possible bitwise OR of the new array.

------ Input Format ------ 

- The first line contains a single integer T - the number of test cases. Then T test cases follow.
- The first line of each test case contains a single integer N - the length of the array.
- The next line contains N integers A_{1},\ldots, A_{N}.

------ Output Format ------ 

For each test case, print two integers: X and the minimum possible bitwise OR of the new array.

If there are multiple values of X that achieve the minimum bitwise OR, print any of them.

------ Constraints ------ 

$1 ≤ T ≤ 5000$
$ 1 ≤ N ≤ 100 $
$ 0 ≤  A_{i} ≤ 10^{9} $

----- Sample Input 1 ------ 
1
2
4 6
----- Sample Output 1 ------ 
6 2
----- explanation 1 ------ 
Here, if we take $X=6$, then our expression would become $(4\oplus 6) \lor (6\oplus 6) = 2\lor 0 = 2$, which is the minimum possible.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Mathematics


Solutions:
def brute(x, arr):
	res = arr[0] ^ x
	for i in range(1, len(arr)):
		res |= arr[i] ^ x
	return res

def soln(n, arr):
	maxm = max(arr)
	return (maxm, brute(maxm, arr))
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(*soln(n, arr))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = max(l)
	r = 0
	for i in range(n):
		l[i] = l[i] ^ m
		r = r | l[i]
	print(m, r)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = 9999999
	for i in l:
		f = 0
		for j in l:
			f = f | j ^ i
		if f <= k:
			k = f
			c = i
	print(str(c) + ' ' + str(k))


from bisect import bisect_left, bisect_right
import math
from bisect import bisect_left
from heapq import heapify, heappush, heappop
from collections import deque
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for i in range(ii()):
	s = ii()
	a = il()
	m = max(a)
	y = 0
	for k in range(s - 1):
		x = a[k] ^ a[k + 1]
		y |= x
	print(m, y)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for i in a:
		c = c | i
	ans = 0
	for i in a:
		ans = ans | i ^ c
	print(c, ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	x = 0
	for i in range(n):
		x = x | arr[i]
	ans = 0
	for i in range(n):
		ans |= arr[i] ^ x
	res = []
	res.append(x)
	res.append(ans)
	print(*res)


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	ende = A[0]
	tot = 0
	for ele in A:
		ende = ende | ele
	for elem in A:
		tot = elem ^ ende | tot
	print(ende, tot)


from functools import reduce
for _ in range(int(input())):
	n = int(input())
	nli = list(map(int, input().split()))
	mx = max(nli)
	xli = list()
	for a in nli:
		xli.append(a ^ mx)
	rs = reduce(lambda x, y: x | y, xli)
	print(mx, rs)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	x = arr[0]
	for i in arr:
		x = x | i
	res = arr[0] ^ x
	ans = res
	for i in range(1, n):
		res = arr[i] ^ x
		ans = ans | res
	print(x, ans)


def decimalToBinary(n):
	return '{0:b}'.format(int(n))

def main():
	t = int(input())
	while t:
		n = int(input())
		list = [int(item) for item in input().split()]
		max = 0
		for i in range(n):
			if list[i] > max:
				max = list[i]
		bin_num = decimalToBinary(max)
		length = len(bin_num)
		high = (1 << length + 1) - 1
		ans = 0
		xor_num = 0
		for i in range(n):
			let_xor = high ^ list[i]
			if let_xor not in list:
				if xor_num < list[i]:
					xor_num = list[i]
		for i in range(n):
			ans = ans | xor_num ^ list[i]
		print(xor_num, ans)
		t -= 1
main()


for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	maxi = max(ar)
	sz = len(bin(maxi)[2:])
	ones = 0
	for i in range(n):
		ones |= ar[i]
	fc = 0
	for j in range(n):
		fc |= ar[j] ^ ones
	print(ones, fc)


T = int(input())
for i in range(T):
	n = int(input())
	L = list(map(int, input().split()))
	x = max(L)
	y = 0
	for i in range(n):
		a = L[i]
		a = a ^ x
		y = y | a
	print(x, y)


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)))

def main():
	for _ in tr():
		n = nl()
		a = ln()
		max_a = max(a)
		min_or = 0
		for i in a:
			min_or |= i ^ max_a
		print(max_a, min_or)
main()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(x, y) = (0, 0)
	for i in l:
		x |= i
	for i in l:
		y |= i ^ x
	print(x, y)


t = int(input())
for _ in range(0, t):
	n = int(input())
	list1 = [int(num) for num in input().split()]
	x = 0
	i = 0
	for i in range(0, len(list1)):
		x = x | list1[i]
	for i in range(0, len(list1)):
		list1[i] = list1[i] ^ x
	f = 0
	for i in range(0, len(list1)):
		f = f | list1[i]
	print(f'{x} {f}')


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	X = 0
	min_ = 0
	for i in arr:
		X |= i
	for i in arr:
		min_ |= X ^ i
	print(X, min_)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	X = 0
	ans = 0
	for i in a:
		X |= i
	for i in a:
		ans |= X ^ i
	print(f'{X} {ans}')


numTest = int(input())
for _ in range(numTest):
	n = input()
	arr = list(map(int, input().split()))
	or_ = 0
	for i in arr:
		or_ |= i
	ans = 0
	for j in arr:
		ans = ans | or_ ^ j
	print(or_, ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	x = max(arr)
	xor = []
	orr = 0
	for i in arr:
		xor.append(i ^ x)
	for i in xor:
		orr = orr | i
	print(str(x) + ' ' + str(orr))


def b(l):
	p = max(l)
	ans = []
	r = len(bin(p))
	for i in range(r - 2):
		ans.append(0)
	for j in range(len(l)):
		t = l[j]
		k = -1
		while t != 0:
			if t & 1 == 1:
				ans[k] = 1
			k = k - 1
			t = t >> 1
	return ans
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	f = b(l)
	final = ''
	for i in f:
		if i == 1:
			final += '1'
		else:
			final += '0'
	x = int(final, 2)
	for i in range(n):
		l[i] = l[i] ^ x
	ans = l[0]
	for i in range(1, n):
		ans = ans | l[i]
	print(x, ans)


def findor(arr, n):
	x = 0
	for i in range(n):
		x = x | arr[i]
	return x
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	x = findor(arr, n)
	for i in range(n):
		arr[i] = arr[i] ^ x
	print(x, findor(arr, n))


T = int(input())
for i in range(T):
	n = int(input())
	arr = [int(X) for X in input().split()]
	a = 0
	for i in arr:
		a = a | i
	res = 0
	for i in arr:
		res = res | a ^ i
	print(a, res)


case = int(input())
for r in range(case):
	n = int(input())
	arr = [int(x) for x in input().split()]
	x = arr[0]
	for i in range(n):
		x = x | arr[i]
	res = 0
	for i in range(n):
		res = res | arr[i] ^ x
	print(x, res)


import sys
for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	Min = sys.maxsize
	ans = 0
	for x in arr:
		cal = 0
		for i in range(n):
			cal = cal | arr[i] ^ x
		Min = min(Min, cal)
		if cal == Min:
			ans = x
	print(ans, Min)


t = int(input())
for i in range(t):
	n = int(input())
	mini = 0
	a = list(map(int, input().split()))
	b = max(a)
	for i in range(n):
		mini = mini | b ^ a[i]
	print(b, mini)


t = int(input())
for i in range(t):
	n = int(input())
	mini = 0
	a = list(map(int, input().split()))
	andi = 0
	for i in range(n):
		andi = andi | a[i]
	for i in range(n):
		mini = mini | andi ^ a[i]
	print(andi, mini)


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	Or = 0
	for i in lst:
		Or |= i
	lst1 = [i ^ Or for i in lst]
	ans = 0
	for i in lst1:
		ans |= i
	print(Or, end=' ')
	print(ans)


try:
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		mx = max(a)
		for i in range(n):
			a[i] = mx ^ a[i]
		res = a[0]
		for i in range(1, n):
			res |= a[i]
		print(mx, res)
except:
	pass


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans1 = 0
	ans2 = 0
	for i in arr:
		ans1 = ans1 | i
	for i in range(n):
		arr[i] = arr[i] ^ ans1
		ans2 = ans2 | arr[i]
	print(ans1, ans2)


tc = int(input())
while tc > 0:
	num = int(input())
	li = list(map(int, input().split()))
	x = 0
	minimum = 0
	for i in li:
		x |= i
	for j in li:
		minimum |= x ^ j
	print(x, minimum)
	tc -= 1


try:
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		x = 0
		ans = 0
		for i in a:
			x |= i
		for i in a:
			ans |= i ^ x
		print(x, ans)
except:
	pass


t = int(input())
for test in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	x = l[0]
	for i in range(1, n):
		x = x | l[i]
	c = l[0] ^ x
	for i in range(1, n):
		c = c | l[i] ^ x
	print(x, c)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = max(l)
	m1 = 0
	for i in l:
		m1 |= m ^ i
	print(m, m1)


try:
	t = int(input())
	while t != 0:
		n = int(input())
		arr = [int(i) for i in input().split()]
		x = max(arr)
		s = []
		y = 0
		for i in range(n):
			arr[i] = arr[i] ^ x
		for i in range(n):
			y = y | arr[i]
		print(x, y)
		t -= 1
except EOFError:
	pass


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	m = max(lst)
	s = 0
	for i in lst:
		s |= i ^ m
	print(f'{m} {s}')


import sys, os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = max(a)
	for i in range(n):
		a[i] = x ^ a[i]
	val = 0
	for i in range(n):
		val = val | a[i]
	print(x, val)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	r = 0
	ans = 0
	for i in l:
		r |= i
	for i in range(n):
		l[i] ^= r
		ans |= l[i]
	print(r, ans)


T = int(input())
while T:
	n = int(input())
	ans = 0
	lst = list(map(int, input().split()))
	X = max(lst)
	for i in lst:
		ans = ans | i ^ X
	print(X, ans)
	T -= 1


test = int(input())
for _ in range(test):
	n = int(input())
	arr = [int(i) for i in input().split()]
	x = max(arr)
	ans = 0
	xor = x
	for i in arr:
		xor = i ^ x
		ans = ans | xor
	print(x, ans)


tc = int(input())
for _ in range(tc):
	n = int(input())
	N = list(map(int, input().split()))
	x = 0
	for i in N:
		x |= i
	N = map(lambda r: r ^ x, N)
	ans = 0
	for i in N:
		ans = ans | i
	print(x, ans)