Chef has 3 hidden numbers A, B, and C such that 0 ≤ A, B, C ≤ N.

Let f be a function such that f(i) = (A \oplus i) + (B \oplus i) + (C \oplus i). Here \oplus denotes the [bitwise XOR] operation.

Given the values of f(0), f(1), \dots, f(N), determine the values of A, B, and C.

It is guaranteed that at least one tuple exists for the given input. If there are multiple valid tuples of A, B, C, print any one.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains a single integer N denoting the upper bound on the values of A, B, C.
- Next line contains N+1 space-separated integers denoting f(0), f(1), \dots, f(N).

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

For each test case, output on a new line, three space-separated integers, the values of A, B, and C. If there are multiple valid tuples of A, B, C, print any one.

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

$1 ≤ T ≤ 2 \cdot 10^{4}$
$2 ≤ N ≤ 10^{5}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
2
0 3 6
2
4 7 2
5
9 6 11 8 13 10

----- Sample Output 1 ------ 
0 0 0
2 0 2
1 3 5

----- explanation 1 ------ 
Test case $1$: The tuple $A = 0, B=0, C=0$ satisfies as:
- $f(0)= 0\oplus 0 + 0\oplus 0 + 0\oplus 0 = 0$.
- $f(1)= 0\oplus 1 + 0\oplus 1 + 0\oplus 1 = 3$.
- $f(2)= 0\oplus 2 + 0\oplus 2 + 0\oplus 2 = 6$.

Test case $2$: The tuple $A = 2, B=0, C=2$ satisfies as:
- $f(0)= 2\oplus 0 + 0\oplus 0 + 2\oplus 0 = 4$.
- $f(1)= 2\oplus 1 + 0\oplus 1 + 2\oplus 1 = 7$.
- $f(2)= 2\oplus 2 + 0\oplus 2 + 2\oplus 2 = 2$.

Test case $3$: The tuple $A = 1, B=3, C=5$ satisfies as:
- $f(0)= 1\oplus 0 + 3\oplus 0 + 5\oplus 0 = 9$.
- $f(1)= 1\oplus 1 + 3\oplus 1 + 5\oplus 1 = 6$.
- $f(2)= 1\oplus 2 + 3\oplus 2 + 5\oplus 2 = 11$.
- $f(3)= 1\oplus 3 + 3\oplus 3 + 5\oplus 3 = 8$.
- $f(4)= 1\oplus 4 + 3\oplus 4 + 5\oplus 4 = 13$.
- $f(5)= 1\oplus 5 + 3\oplus 5 + 5\oplus 5 = 10$.

Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Mathematics

Greedy algorithms
Skill types: Bit manipulation

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	num = int(input())
	lis = list(map(int, input().split()))
	bigl = [0, 0, 0]
	for i in range(20, -1, -1):
		if 2 ** i > num:
			continue
		bigl = list(sorted(bigl))
		mount = (3 - (lis[2 ** i] - lis[0]) // 2 ** i) // 2
		for j in range(mount):
			bigl[j] += 2 ** i
	print(bigl[0], bigl[1], bigl[2])


from sys import stdin, stdout
from collections import defaultdict, Counter, deque
import math, heapq, bisect
input = stdin.readline

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def lcm(a, b):
	return a * b // math.gcd(a, b)

def gcd(a, b):
	return math.gcd(a, b)

def gcd_list_of_elements(li):
	n = len(li)
	res = li[0]
	for i in range(1, n):
		res = math.gcd(res, li[i])
	return res

def isPalindrome(x):
	x = str(x)
	return x == x[::-1]

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class FenwickTreeSum:

	def __init__(self, arr):
		self.n = len(arr)
		self.f = [0] * self.n
		for (i, x) in enumerate(arr):
			self.increment(i, x)

	def increment(self, j, v):
		while j < self.n:
			self.f[j] += v
			j = j | j + 1

	def range_sum(self, l, r):
		return self.prefix_sum(r - 1) - self.prefix_sum(l - 1)

	def prefix_sum(self, x):
		z = x
		res = 0
		while z >= 0:
			res += self.f[z]
			z = (z & z + 1) - 1
		return res
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	ans = [0, 0, 0]
	for i in range(int(math.log2(n)), -1, -1):
		pw = 1 << i
		set_bits = (3 + (a[0] - a[pw]) // pw) // 2
		ans.sort()
		for i in range(set_bits):
			ans[i] += pw
	print(*ans)


import sys
import os
import math
import collections
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	B = A[0]
	val = 1
	ans = [0] * 3
	while 2 * val <= N:
		val *= 2
	i = val
	while i > 0:
		C = i
		if B >= A[C]:
			cnt = (B - A[C]) // C
			if cnt == 3:
				ans[0] += C
				ans[1] += C
				ans[2] += C
			else:
				ans[0] += C
				ans[1] += C
		else:
			cnt = abs(B - A[C]) // C
			if cnt == 1:
				ans[0] += C
		i //= 2
		ans.sort()
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	L = [0, 0, 0]
	for i in range(20, -1, -1):
		if 2 ** i > n:
			continue
		L = list(sorted(L))
		delta = (3 - (arr[2 ** i] - arr[0]) // 2 ** i) // 2
		for j in range(delta):
			L[j] += 2 ** i
	print(L[0], L[1], L[2])


t = int(input())
for tt in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	a = int(0)
	b = int(0)
	c = int(0)
	pp = 0
	for pp in range(2000):
		pp = pp + 1
	for i in range(20):
		if 2 ** i > n:
			break
		delta = int(arr[2 ** i] - arr[0])
		delta = int(delta / 2 ** i)
		if delta == -3:
			a = a + 2 ** i
			b = b + 2 ** i
			c = c + 2 ** i
		elif delta == -1:
			a = a + 2 ** i
			b = b + 2 ** i
		elif delta == 1:
			a = a + 2 ** i
		else:
			cv = 0
			cv = cv + 1
	if a > n:
		j = 20
		for i in reversed(range(21)):
			k = 2 ** i
			if k & a == 0:
				continue
			if b & k and c & k:
				continue
			a = a - k
			c = c + k
			j = i
			break
		if b > n:
			for i in reversed(range(j)):
				k = 2 ** i
				if k & b == 0:
					continue
				if a & k and c & k:
					continue
				if a & k == 0:
					a = a + k
					b = b - k
					break
				else:
					if c + k > n:
						continue
					b = b - k
					c = c + k
					break
	print(a, b, c)


import math
for t in range(int(input())):
	n = int(input())
	f = list((int(i) for i in input().split()))
	(a, b, c) = (0, 0, 0)
	x = int(math.log(n, 2))
	k = pow(2, x)
	while k > 0:
		if f[k] + 3 * k == f[0]:
			a += k
			b += k
			c += k
		elif f[k] + k == f[0]:
			if c == max(a, b, c):
				a += k
				b += k
			elif b == max(a, b, c):
				a += k
				c += k
			else:
				b += k
				c += k
		elif f[k] == f[0] + k:
			if a == min(a, b, c):
				a += k
			elif b == min(a, b, c):
				b += k
			else:
				c += k
		k = k // 2
	if max(a, b, c) > n:
		raise
	print(a, b, c)


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = [0, 0, 0]
	s_b = 0
	for i in range(20, -1, -1):
		if 1 << i & n:
			s_b = i
			break
	for i in range(s_b, -1, -1):
		num = 1 << i
		diff = l[0] - l[num]
		ns_b = diff // num
		ns_b = int((3 + ns_b) // 2)
		a.sort()
		t = 0
		for j in range(3):
			if a[j] + num > n:
				continue
			if t == ns_b:
				break
			a[j] += num
			t += 1
	print(*a, sep=' ')


for _ in range(int(input())):
	n = int(input())
	ll = list(map(int, input().split()))
	x = ll[0]
	mm = min(ll)
	c = ll.index(mm)
	ok = False
	if x == 0:
		print(0, 0, 0)
		ok = True
	for a in range(x + 1):
		if ok:
			break
		b = x - c - a
		for i in range(n + 1):
			if (a ^ i) + (b ^ i) + (c ^ i) != ll[i] or max(a, b, c) > n:
				break
			elif i == n:
				print(b, a, c)
				ok = True
				break


for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(a, b, c) = ([], [], [])
	(isA, isB, isC) = (False, False, False)
	nbin = bin(n)[2:]
	d = len(nbin)
	i = 0
	curr = 2 ** (d - 1)
	while i < d:
		diff = (arr[curr] - arr[0]) // curr
		if diff == 3:
			if nbin[i] == '1':
				(isA, isB, isC) = (True, True, True)
			a.append('0')
			b.append('0')
			c.append('0')
		if diff == 1:
			if isA:
				a.append('1')
				b.append('0')
				c.append('0')
				if nbin[i] == '1':
					(isB, isC) = (True, True)
			elif isB:
				a.append('0')
				b.append('1')
				c.append('0')
				if nbin[i] == '1':
					(isA, isC) = (True, True)
			else:
				a.append('0')
				b.append('0')
				c.append('1')
				if nbin[i] == '1':
					(isA, isB) = (True, True)
		if diff == -1:
			if not isA:
				a.append('0')
				b.append('1')
				c.append('1')
				if nbin[i] == '1':
					isA = True
			elif not isB:
				a.append('1')
				b.append('0')
				c.append('1')
				if nbin[i] == '1':
					isB = True
			else:
				a.append('1')
				b.append('1')
				c.append('0')
				if nbin[i] == '1':
					isC = True
		if diff == -3:
			a.append('1')
			b.append('1')
			c.append('1')
		i += 1
		curr //= 2
	(x, y, z) = (int(''.join(a), 2), int(''.join(b), 2), int(''.join(c), 2))
	print(x, y, z)


import math
for _ in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	x = [0, 0, 0]
	n_mx = 0
	for i in range(20, -1, -1):
		if 1 << i & n:
			n_mx = i
			break
	for i in range(n_mx, -1, -1):
		num = 1 << i
		delta = f[0] - f[num]
		cnt = delta // num
		cnt = int((3 + cnt) // 2)
		x.sort()
		tmp = 0
		for j in range(3):
			if x[j] + num > n:
				continue
			if tmp == cnt:
				break
			x[j] += num
			tmp += 1
	print(*x, sep=' ')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	li2 = [0, 0, 0]
	temp1 = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			temp1 = i
			break
	j = temp1
	while j > 0:
		x = a[j] - a[0]
		if x < 0:
			x = x * -1
			count = x // j
			if count == 1:
				count = 2
				if li2[0] ^ j <= n:
					li2[0] ^= j
					count = count - 1
				if count & (li2[1] ^ j) <= n:
					li2[1] ^= j
					count = count - 1
				if count > 0 & (li2[2] ^ j <= n):
					li2[2] ^= j
			elif count == 3:
				li2[0] ^= j
				li2[1] ^= j
				li2[2] ^= j
		else:
			count = x // j
			if count == 1:
				if li2[0] ^ j <= n:
					li2[0] ^= j
				elif li2[1] ^ j <= n:
					li2[1] ^= j
				else:
					li2[2] ^= j
		li2.sort()
		j //= 2
	for i in range(len(li2)):
		print(li2[i], end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			res = i
			break
	val = [0] * 3
	i = res
	while i > 0:
		dif = l[i] - l[0]
		if dif < 0:
			dif = dif * -1
			c = dif // i
			if c == 1:
				c = 2
				if val[0] ^ i <= n:
					val[0] = val[0] ^ i
					c -= 1
				if c and val[1] ^ i <= n:
					val[1] ^= i
					c -= 1
				if c > 0 and val[2] ^ i <= n:
					val[2] ^= i
			elif c == 3:
				val[0] ^= i
				val[1] ^= i
				val[2] ^= i
		else:
			c = dif // i
			if c == 1:
				if val[0] ^ i <= n:
					val[0] ^= i
				elif val[1] ^ i <= n:
					val[1] ^= i
				else:
					val[2] ^= i
		i = i // 2
		val.sort()
	for i in val:
		print(i, end=' ')
	print()


def fun(n):
	ans = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			ans = i
			break
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	arr = [0, 0, 0]
	i = fun(n)
	while i > 0:
		diff = a[i] - a[0]
		if diff < 0:
			diff *= -1
			b = diff / i
			if b == 1:
				b = 2
				if arr[0] ^ i <= n:
					arr[0] ^= i
					b -= 1
				if b and arr[1] ^ i <= n:
					arr[1] ^= i
					b -= 1
				if b > 0 and arr[2] ^ i <= n:
					arr[2] ^= i
			elif b == 3:
				arr[0] ^= i
				arr[1] ^= i
				arr[2] ^= i
		else:
			b = diff / i
			if b == 1:
				if arr[0] ^ i <= n:
					arr[0] ^= i
				elif arr[1] ^ 1 <= n:
					arr[1] ^= i
				else:
					arr[2] ^= i
		i = int(i / 2)
		arr = sorted(arr)
	print(*arr)


def max2pow(n):
	po = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			po = i
			break
	return po
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = [0, 0, 0]
	i = max2pow(n)
	while i > 0:
		diff = arr[i] - arr[0]
		if diff < 0:
			diff *= -1
			ct = diff // i
			if ct == 1:
				ct = 2
				if ans[0] ^ i <= n:
					ans[0] = ans[0] ^ i
					ct -= 1
				if ct and ans[1] ^ i <= n:
					ans[1] = ans[1] ^ i
					ct -= 1
				if ct > 0 and ans[2] ^ i <= n:
					ans[2] = ans[2] ^ i
			elif ct == 3:
				ans[0] = ans[0] ^ i
				ans[1] = ans[1] ^ i
				ans[2] = ans[2] ^ i
		else:
			ct = diff // i
			if ct == 1:
				if ans[0] ^ i <= n:
					ans[0] = ans[0] ^ i
				elif ans[1] ^ i <= n:
					ans[1] = ans[1] ^ i
				else:
					ans[2] = ans[2] ^ i
		ans.sort()
		i = i // 2
	print(f'{ans[0]} {ans[1]} {ans[2]}')


def highestpowerof2(n):
	res = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			res = i
			break
	return res
for test in range(int(input())):
	n = int(input())
	arr = [int(char) for char in input().split()]
	ans = [0, 0, 0]
	i = highestpowerof2(n)
	while i >= 1:
		diff = arr[i] - arr[0]
		if diff < 0:
			diff *= -1
			ct = diff // i
			if ct == 1:
				ct = 2
				if ans[0] ^ i <= n:
					ans[0] ^= i
					ct -= 1
				if (ct and ans[1] ^ i) <= n:
					ans[1] ^= i
					ct -= 1
				if ct > 0 and ans[2] ^ i <= n:
					ans[2] ^= i
			elif ct == 3:
				ans[0] ^= i
				ans[1] ^= i
				ans[2] ^= i
		else:
			ct = diff / i
			if ct == 1:
				if ans[0] ^ i <= n:
					ans[0] ^= i
				elif ans[1] ^ i <= n:
					ans[1] ^= i
				else:
					ans[2] ^= i
		ans.sort()
		i = i // 2
	print(ans[0], ans[1], ans[2])


def find_p(p):
	for i in range(p, 0, -1):
		if i & i - 1 == 0:
			return i
for _ in range(int(input())):
	n = int(input())
	li = [int(i) for i in input().split()]
	i = find_p(n)
	res = [0] * 3
	while i > 0:
		d = li[i] - li[0]
		if d < 0:
			d *= -1
			c = d / i
			if c == 1:
				c = 2
				if res[0] ^ i <= n:
					res[0] ^= i
					c -= 1
				if c and res[1] ^ i <= n:
					res[1] ^= i
					c -= 1
				if c > 0 and res[2] ^ i <= n:
					res[2] ^= i
			elif c == 3:
				res[0] ^= i
				res[1] ^= i
				res[2] ^= i
		else:
			c = d / i
			if c == 1:
				if res[0] ^ i <= n:
					res[0] ^= i
				elif res[1] ^ i <= n:
					res[1] ^= i
				else:
					res[2] ^= i
		res.sort()
		i = int(i / 2)
	print(res[0], res[1], res[2])


def power(n):
	ans = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			ans = i
			break
	return ans
t = int(input())
while t > 0:
	n = int(input())
	f = list(map(int, input().split()))
	ans = [0, 0, 0]
	i = power(n)
	while i > 0:
		diff = f[i] - f[0]
		if diff < 0:
			diff *= -1
			x = diff // i
			if x == 1:
				x = 2
				if ans[0] ^ i <= n:
					ans[0] ^= i
					x -= 1
				if x != 0 and ans[1] ^ i <= n:
					ans[1] ^= i
					x -= 1
				if x > 0 and ans[2] ^ i <= n:
					ans[2] ^= i
			elif x == 3:
				ans[0] ^= i
				ans[1] ^= i
				ans[2] ^= i
		else:
			x = diff // i
			if x == 1:
				if ans[0] ^ i <= n:
					ans[0] ^= i
				elif ans[1] ^ i <= n:
					ans[1] ^= i
				else:
					ans[2] ^= i
		ans.sort()
		i = i // 2
	print(ans[0], ans[1], ans[2])
	t = t - 1


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = [0, 0, 0]
	power = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			power = i
			break
	j = power
	while j > 0:
		x = a[j] - a[0]
		if x < 0:
			x = x * -1
			c = x // j
			if c == 1:
				c = 2
				if ans[0] ^ j <= n:
					ans[0] ^= j
					c = c - 1
				if c & (ans[1] ^ j) <= n:
					ans[1] ^= j
					c = c - 1
				if c > 0 & (ans[2] ^ j <= n):
					ans[2] ^= j
			elif c == 3:
				ans[0] ^= j
				ans[1] ^= j
				ans[2] ^= j
		else:
			c = x // j
			if c == 1:
				if ans[0] ^ j <= n:
					ans[0] ^= j
				elif ans[1] ^ j <= n:
					ans[1] ^= j
				else:
					ans[2] ^= j
		ans.sort()
		j //= 2
	for i in ans:
		print(i, end=' ')
	print()


def max2power(n):
	res = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			res = i
			break
	return res
for _ in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	ans = [0, 0, 0]
	i = max2power(n)
	while i > 0:
		dif = f[i] - f[0]
		if dif < 0:
			dif = abs(dif)
			c = int(dif / i)
			if c == 1:
				c = 2
				if ans[0] ^ i <= n:
					ans[0] = ans[0] ^ i
					c -= 1
				if c and ans[1] ^ i <= n:
					ans[1] = ans[1] ^ i
					c -= 1
				if c > 0 and ans[2] ^ i <= n:
					ans[2] = ans[2] ^ i
			elif c == 3:
				ans[0] = ans[0] ^ i
				ans[1] = ans[1] ^ i
				ans[2] = ans[2] ^ i
		else:
			c = int(dif / i)
			if c == 1:
				if ans[0] ^ i <= n:
					ans[0] = ans[0] ^ i
				elif ans[1] ^ i <= n:
					ans[1] = ans[1] ^ i
				else:
					ans[2] = ans[2] ^ i
		i = int(i / 2)
		ans.sort()
	print(*ans)


def check(n):
	po = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			po = i
			break
	return po
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	val = [0, 0, 0]
	i = check(n)
	while i > 0:
		diff = a[i] - a[0]
		if diff < 0:
			diff *= -1
			cons = diff // i
			if cons == 1:
				cons = 2
				if val[0] ^ i <= n:
					val[0] ^= i
					cons -= 1
				if cons and val[1] ^ i <= n:
					val[1] ^= i
					cons -= 1
				if cons > 0 and val[2] ^ i <= n:
					val[2] ^= i
			elif cons == 3:
				val[0] ^= i
				val[1] ^= i
				val[2] ^= i
		else:
			cons = diff // i
			if cons == 1:
				if val[0] ^ i <= n:
					val[0] ^= i
				elif val[1] ^ i <= n:
					val[1] ^= i
				else:
					val[2] ^= i
		val = sorted(val)
		i = i // 2
	print(val[0], val[1], val[2])


def hp(n):
	res = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			res = i
			break
	return res
T = int(input())
while T > 0:
	T -= 1
	n = int(input())
	st = input()
	st = st.split(' ')
	st = [int(i) for i in st]
	ans = [0, 0, 0]
	i = hp(n)
	while i > 0:
		dif = st[i] - st[0]
		if dif < 0:
			dif *= -1
			ct = dif // i
			if ct == 1:
				ct = 2
				if ans[0] ^ i <= n:
					ans[0] ^= i
					ct -= 1
				if ct and ans[1] ^ i <= n:
					ans[1] ^= i
					ct -= 1
				if ct > 0 and ans[2] ^ i <= n:
					ans[2] ^= i
					ct -= 1
			elif ct == 3:
				ans[0] ^= i
				ans[1] ^= i
				ans[2] ^= i
		else:
			ct = dif / i
			if ct == 1:
				if ans[0] ^ i <= n:
					ans[0] ^= i
				elif ans[1] ^ i <= n:
					ans[1] ^= i
				else:
					ans[2] ^= i
		ans.sort()
		i = i // 2
	print(ans[0], ans[1], ans[2])


def power(n):
	ans = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			ans = i
			break
	return ans
for ts in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	ans = [0] * 3
	i = power(n)
	while i > 0:
		d = ls[i] - ls[0]
		if d < 0:
			d *= -1
			ct = d // i
			if ct == 1:
				ct = 2
				if ans[0] ^ i <= n:
					ans[0] ^= i
					ct -= 1
				if ct and ans[1] ^ i <= n:
					ans[1] ^= i
					ct -= 1
				if ct > 0 and ans[2] ^ i <= n:
					ans[2] ^= i
			elif ct == 3:
				ans[0] ^= i
				ans[1] ^= i
				ans[2] ^= i
		else:
			ct = d // i
			if ct == 1:
				if ans[0] ^ i <= n:
					ans[0] ^= i
				elif ans[1] ^ i <= n:
					ans[1] ^= i
				else:
					ans[2] ^= i
		i = i // 2
		ans.sort()
	print(ans[0], ans[1], ans[2])


import math
import itertools

def finc_max(n):
	result = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			result = i
			break
	return result

def functionmax(a, b):
	return min(a, a ^ b)
t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	arr = list(map(int, input().split()))
	zero_3 = []
	for i in range(0, 3):
		zero_3.append(0)
	a = arr[0]
	b = arr[1]

	def printt(output):
		print(*output)
	final_res = zero_3

	def xorfunction(n, i):
		return n ^ i
	i = finc_max(n)
	ac = 0
	left = 0
	right = n
	while i > 0:
		minus_1_2 = arr[i] - arr[0]
		if minus_1_2 < 0:
			minus_1_2 = minus_1_2 * -1
			ac = ac + 1
			pointer = int(minus_1_2 / i)
			if pointer == 1:
				left = left + 1
				pointer = 2
				ac = ac - 1
				if final_res[0] ^ i <= n:
					final_res[0] = final_res[0] ^ i
					pointer = pointer - 1
				if pointer and final_res[1] ^ i <= n:
					c = functionmax(a, b)
					if c > 0:
						c = c - 1
					else:
						c = c * 2
						ac = ac + 1
					final_res[1] = xorfunction(final_res[1], i)
					pointer = pointer - 1
				if pointer > 0 and final_res[2] ^ i <= n:
					right = right - 1
					final_res[2] = xorfunction(final_res[2], i)
					mid = right // 2
					pointer = pointer - 1
			elif pointer == 3:
				ac = ac * -1
				final_res[0] = xorfunction(final_res[0], i)
				final_res[1] = xorfunction(final_res[1], i)
				final_res[2] = xorfunction(final_res[2], i)
		else:
			ac = ac + 1
			c = functionmax(a, b)
			if c > 0:
				c = c - 1
			else:
				c = c * 2
			pointer = int(minus_1_2 / i)
			if pointer == 1:
				if final_res[0] ^ i <= n:
					final_res[0] ^= i
				elif final_res[1] ^ i <= n:
					final_res[1] ^= i
				else:
					final_res[2] ^= i
		i = i // 2
		final_res.sort()
	printt(final_res)


t = int(input())
for _ in range(t):
	n = int(input())
	f = list(map(int, input().split()))
	abc = [0, 0, 0]
	j = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			j = i
			break
	while j > 0:
		diff = f[j] - f[0]
		if diff < 0:
			diff *= -1
			count = diff // j
			if count == 1:
				count = 2
				if abc[0] ^ j <= n:
					abc[0] ^= j
					count -= 1
				if count != 0 and abc[1] ^ j <= n:
					abc[1] ^= j
					count -= 1
				if count != 0 and abc[2] ^ j <= n:
					abc[2] ^= j
			elif count == 3:
				(abc[0], abc[1], abc[2]) = (abc[0] ^ j, abc[1] ^ j, abc[2] ^ j)
		else:
			count = diff // j
			if count == 1:
				if abc[0] ^ j <= n:
					abc[0] ^= j
				elif abc[1] ^ j <= n:
					abc[1] ^= j
				else:
					abc[2] ^= j
		abc.sort()
		j = j // 2
	print(*abc, sep=' ', end='\n')


t = int(input())
while t:
	n = int(input())
	array = list(map(int, input().split()))
	for j in range(n, 0, -1):
		if j & j - 1 == 0:
			i = j
			break
	res = [0, 0, 0]
	while i > 0:
		temp = 0
		m = array[i] - array[0]
		if m < 0:
			m *= -1
			calino = m / i
			if calino == 1:
				calino = 2
				for alpha in range(10):
					temp += alpha
				if res[0] ^ i <= n:
					res[0] ^= i
					calino -= 1
				if calino and res[1] ^ i <= n:
					res[1] ^= i
					calino -= 1
				if calino > 0 and res[2] ^ i <= n:
					res[2] ^= i
			elif calino == 3:
				for alpha in range(10):
					temp += alpha
				res[0] ^= i
				res[1] ^= i
				res[2] ^= i
		else:
			for alpha in range(10):
				temp += alpha
			calino = m / i
			if calino == 1:
				for alpha in range(10):
					temp += alpha
				if res[0] ^ i <= n:
					res[0] ^= i
				elif res[1] ^ i <= n:
					res[1] ^= i
				else:
					res[2] ^= i
		temp = temp - res[0]
		res.sort()
		i = int(i / 2)
	name = 'yashvardhan'
	print(*res)
	t -= 1
name += ' Rathore'


def check(x, y, z, b):
	for i in range(len(b)):
		if (x ^ i) + (y ^ i) + (z ^ i) != b[i]:
			return False
	return True
for x in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	if 0 in b:
		c = b.index(0)
		print(c, c, c)
	else:
		c = b.index(min(b))
		d = b[0] - c
		l = d // 2
		r = d // 2 + d % 2
		while l >= 0 and r <= a + 1:
			if check(c, l, r, b):
				print(c, l, r)
				break
			l -= 1
			r += 1


def highestPowerOf2(n):
	res = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			return i
t = int(input())
while t:
	n = int(input())
	lis = [int(i) for i in input().strip().split(' ')]
	ans = [0] * 3
	i = highestPowerOf2(n)
	while i > 0:
		diff = lis[i] - lis[0]
		if diff < 0:
			diff *= -1
			count = diff // i
			if count == 1:
				count = 2
				if ans[0] ^ i <= n:
					ans[0] ^= i
					count -= 1
				if count and ans[1] ^ i <= n:
					ans[1] ^= i
					count -= 1
				if count > 0 and ans[2] ^ i <= n:
					ans[2] ^= i
			elif count == 3:
				ans[0] ^= i
				ans[1] ^= i
				ans[2] ^= i
		else:
			count = diff // i
			if count == 1:
				if ans[0] ^ i <= n:
					ans[0] ^= i
				elif ans[1] ^ i <= n:
					ans[1] ^= i
				else:
					ans[2] ^= i
		ans.sort()
		i //= 2
	print(ans[0], ans[1], ans[2])
	t -= 1


t = int(input())
while t:
	n = int(input())
	array = list(map(int, input().split()))

	def func(n):
		val = 0
		for i in range(n, 0, -1):
			if i & i - 1 == 0:
				val = i
				break
		return val
	res = [0, 0, 0]
	i = func(n)
	while i > 0:
		minus = array[i] - array[0]
		if minus < 0:
			minus *= -1
			ct = minus / i
			if ct == 1:
				ct = 2
				if res[0] ^ i <= n:
					res[0] ^= i
					ct -= 1
				if ct and res[1] ^ i <= n:
					res[1] ^= i
					ct -= 1
				if ct > 0 and res[2] ^ i <= n:
					res[2] ^= i
			elif ct == 3:
				res[0] ^= i
				res[1] ^= i
				res[2] ^= i
		else:
			ct = minus / i
			if ct == 1:
				if res[0] ^ i <= n:
					res[0] ^= i
				elif res[1] ^ i <= n:
					res[1] ^= i
				else:
					res[2] ^= i
		res.sort()
		i = int(i / 2)
	print(res[0], res[1], res[2], sep=' ')
	t -= 1


for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	i = 1
	while i <= n:
		if i << 1 > n:
			break
		else:
			i = i << 1
	ans = [0, 0, 0]
	while i > 0:
		k = arr[i] - arr[0]
		if k < 0:
			k *= -1
			z = k // i
			if z == 3:
				ans[0] ^= i
				ans[1] ^= i
				ans[2] ^= i
			elif z == 1:
				z = 2
				if ans[0] ^ i <= n:
					ans[0] ^= i
					z -= 1
				if z and ans[1] ^ i <= n:
					ans[1] ^= i
					z -= 1
				if z > 0 and ans[2] ^ i <= n:
					ans[2] ^= i
		else:
			z = k // i
			if z == 1:
				if ans[0] ^ i <= n:
					ans[0] ^= i
				elif ans[1] ^ i <= n:
					ans[1] ^= i
				else:
					ans[2] ^= i
		i = i // 2
		ans.sort()
	print(*ans, sep=' ')


import io
import os
import sys
import math
sys.setrecursionlimit(10000000)
for _ in range(int(input())):
	n = int(input())
	func_arr = list(map(int, input().split()))
	abc_arr = [0, 0, 0]
	cur_pow2 = 2 ** int(math.log2(n))
	while cur_pow2 > 0:
		cur_difference = func_arr[cur_pow2] - func_arr[0]
		if cur_difference < 0:
			cur_difference = abs(cur_difference)
			cur = cur_difference // cur_pow2
			if cur == 1:
				cur = 2
				if abc_arr[0] ^ cur_pow2 <= n:
					abc_arr[0] ^= cur_pow2
					cur -= 1
				if cur and abc_arr[1] ^ cur_pow2 <= n:
					abc_arr[1] ^= cur_pow2
					cur -= 1
				if cur > 0 and abc_arr[2] ^ cur_pow2 <= n:
					abc_arr[2] ^= cur_pow2
			elif cur == 3:
				abc_arr[0] ^= cur_pow2
				abc_arr[1] ^= cur_pow2
				abc_arr[2] ^= cur_pow2
		else:
			cur = cur_difference // cur_pow2
			if cur == 1:
				if abc_arr[0] ^ cur_pow2 <= n:
					abc_arr[0] ^= cur_pow2
				elif abc_arr[1] ^ cur_pow2 <= n:
					abc_arr[1] ^= cur_pow2
				else:
					abc_arr[2] ^= cur_pow2
		cur_pow2 = cur_pow2 // 2
		abc_arr.sort()
	print(*abc_arr)


def msb(n):
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			return i
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = [0, 0, 0]
	i = msb(n)
	while i > 0:
		d = arr[i] - arr[0]
		if d < 0:
			d *= -1
			ct = d // i
			if ct == 1:
				ct = 2
				if ans[0] ^ i <= n:
					ans[0] ^= i
					ct -= 1
				if ans[1] ^ i <= n:
					ans[1] ^= i
					ct -= 1
				if ct and ans[2] ^ i <= n:
					ans[2] ^= i
			elif ct == 3:
				ans[0] ^= i
				ans[1] ^= i
				ans[2] ^= i
		else:
			ct = d // i
			if ct == 1:
				if ans[0] ^ i <= n:
					ans[0] ^= i
				elif ans[2] ^ i <= n:
					ans[1] ^= i
				else:
					ans[2] ^= i
		ans = ans[:3]
		ans.sort()
		i //= 2
	print('{} {} {}'.format(ans[0], ans[1], ans[2]))


def fun(n):
	res = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			res = i
			break
	return res
t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	ans = [0, 0, 0]
	i = fun(n)
	while i > 0:
		d = l[i] - l[0]
		if d < 0:
			d *= -1
			ct = d // i
			if ct == 1:
				ct = 2
				if ans[0] ^ i <= n:
					ans[0] ^= i
					ct -= 1
				if ct and ans[1] ^ i <= n:
					ans[1] ^= i
					ct -= 1
				if ct > 0 and ans[2] ^ i <= n:
					ans[2] ^= i
			elif ct == 3:
				ans[0] ^= i
				ans[1] ^= i
				ans[2] ^= i
		else:
			ct = d // i
			if ct == 1:
				if ans[0] ^ i <= n:
					ans[0] ^= i
				elif ans[1] ^ i <= n:
					ans[1] ^= i
				else:
					ans[2] ^= i
		ans.sort()
		i //= 2
	print(*ans)
	t -= 1


def pow_highest(n):
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			return i
for _ in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	ans = [0] * 3
	i = pow_highest(n)
	while i > 0:
		diff = f[i] - f[0]
		if diff < 0:
			ct = -diff // i
			if ct == 1:
				ct = 2
				if ans[0] ^ i <= n:
					ans[0] = ans[0] ^ i
					ct -= 1
				if ct > 0 and ans[1] ^ i <= n:
					ans[1] = ans[1] ^ i
					ct -= 1
				if ct > 0 and ans[2] ^ i <= n:
					ans[2] = ans[2] ^ i
			elif ct == 3:
				ans[0] = ans[0] ^ i
				ans[1] = ans[1] ^ i
				ans[2] = ans[2] ^ i
		else:
			ct = diff // i
			if ct == 1:
				if ans[0] ^ i <= n:
					ans[0] = ans[0] ^ i
				elif ans[1] ^ i <= n:
					ans[1] = ans[1] ^ i
				else:
					ans[2] = ans[2] ^ i
		ans.sort()
		i = i // 2
	print(*ans)


def power(num):
	ans = 0
	for i in range(num, 0, -1):
		if i & i - 1 == 0:
			ans = i
			break
	return ans
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = [0, 0, 0]
	i = power(n)
	while i > 0:
		diff = arr[i] - arr[0]
		if diff < 0:
			diff *= -1
			ct = diff // i
			if ct == 1:
				ct = 2
				if ans[0] ^ i <= n:
					ans[0] ^= i
					ct -= 1
				if ct and ans[1] ^ i <= n:
					ans[1] ^= i
					ct -= 1
				if ct > 0 and ans[2] ^ i <= n:
					ans[2] ^= i
			elif ct == 3:
				ans[0] ^= i
				ans[1] ^= i
				ans[2] ^= i
		else:
			ct = diff // i
			if ct == 1:
				if ans[0] ^ i <= n:
					ans[0] ^= i
				elif ans[1] ^ i <= n:
					ans[1] ^= i
				else:
					ans[2] ^= i
		i = i // 2
		ans.sort()
	print(ans[0], ans[1], ans[2])


def maxPowOf2(n):
	while n:
		if n & n - 1 == 0:
			return n
		n -= 1
	return 1
t = int(input())
while t:
	t -= 1
	n = int(input())
	x = list(map(int, input().split()))
	s = x[0]
	idx = maxPowOf2(n)
	ans = [0, 0, 0]
	while idx > 0:
		ans.sort()
		if s > x[idx]:
			noOfOnes = (s - x[idx]) // idx
			for i in range(noOfOnes):
				ans[i] = ans[i] + idx
			if noOfOnes == 1:
				ans[1] = ans[1] + idx
		elif (x[idx] - s) // idx < 3:
			ans[0] = ans[0] + idx
		idx //= 2
	for i in ans:
		if i > n:
			while 1:
				print('hlnow')
		print(i, end=' ')
	print('')


def high(n):
	res = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			res = i
			break
	return res
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	arr.append(0)
	ans = [0, 0, 0]
	i = high(n)
	while i > 0:
		diff = arr[i] - arr[0]
		if diff < 0:
			diff *= -1
			ct = diff // i
			if ct == 1:
				ct = 2
				if ans[0] ^ i <= n:
					ans[0] = ans[0] ^ i
					ct -= 1
				if ct and ans[1] ^ i <= n:
					ans[1] ^= i
					ct -= 1
				if ct > 0 and ans[2] ^ i <= n:
					ans[2] ^= i
			elif ct == 3:
				ans[0] ^= i
				ans[1] ^= i
				ans[2] ^= i
		else:
			ct = diff // i
			if ct == 1:
				if ans[0] ^ i <= n:
					ans[0] ^= i
				elif ans[1] ^ i <= n:
					ans[1] ^= i
				else:
					ans[2] ^= i
		i //= 2
		ans.sort()
	print(*ans)


def hp(n):
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			return i
			break
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = [0] * 3
	i = hp(n)
	while i > 0:
		diff = a[i] - a[0]
		if diff < 0:
			diff = abs(diff)
			ct = diff // i
			if ct == 1:
				ct = 2
				if ans[0] ^ i <= n:
					ans[0] = ans[0] ^ i
					ct -= 1
				if ans[1] ^ i <= n and ct <= n:
					ans[1] = ans[1] ^ i
					ct -= 1
				if ct > 0 and ans[2] ^ i <= n:
					ans[2] = ans[2] ^ i
					ct -= 1
			elif ct == 3:
				ans[0] = ans[0] ^ i
				ans[1] = ans[1] ^ i
				ans[2] = ans[2] ^ i
		else:
			ct = diff // i
			if ct == 1:
				if ans[0] ^ i <= n:
					ans[0] = ans[0] ^ i
				elif ans[1] ^ i <= n:
					ans[1] = ans[1] ^ i
				else:
					ans[2] = ans[2] ^ i
		i = i // 2
		ans.sort()
	print(ans[0], ans[1], ans[2])


def power2(n):
	res = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			res = i
			break
	return res
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	arr = [0, 0, 0]
	x = power2(n)
	while x > 0:
		dif = l[x] - l[0]
		if dif < 0:
			dif *= -1
			ct = dif / x
			if ct == 1:
				ct = 2
				if arr[0] ^ x <= n:
					arr[0] ^= x
					ct = ct - 1
				if (ct and arr[1] ^ x) <= n:
					arr[1] ^= x
					ct = ct - 1
				if ct > 0 and arr[2] ^ x <= n:
					arr[2] **= x
			elif ct == 3:
				arr[0] ^= x
				arr[1] ^= x
				arr[2] ^= x
		else:
			ct = dif / x
			if ct == 1:
				if arr[0] ^ x <= n:
					arr[0] ^= x
				elif arr[1] ^ x <= n:
					arr[1] ^= x
				else:
					arr[2] ^= x
		x = x // 2
		arr.sort()
	print(arr[0], arr[1], arr[2])


import math

def Log2(x):
	if x == 0:
		return False
	return math.log10(x) / math.log10(2)

def power2checker(n):
	if math.ceil(Log2(n)) == math.floor(Log2(n)):
		return True
	else:
		return False

def hpowercal(n):
	ans = 0
	for i in range(n, 0, -1):
		if power2checker(i) == True:
			ans = i
			break
	return ans
for i in range(int(input())):
	x = int(input())
	arr = list(map(int, input().split(' ')))
	final = [0] * 3
	temp = hpowercal(x)
	while temp > 0:
		sub = arr[temp] - arr[0]
		if sub < 0:
			sub = sub * -1
			cross_check = sub // temp
			if cross_check == 1:
				cross_check = 2
				if final[0] ^ temp <= x:
					final[0] = final[0] ^ temp
					cross_check -= 1
				if cross_check > 0 and final[1] ^ temp <= x:
					final[1] = final[1] ^ temp
					cross_check -= 1
				if cross_check > 0 and final[2] ^ i <= x:
					final[2] = final[2] ^ temp
			elif cross_check == 3:
				final[0] ^= temp
				final[1] ^= temp
				final[2] ^= temp
		else:
			cross_check = sub // temp
			if cross_check == 1:
				if final[0] ^ temp <= x:
					final[0] = final[0] ^ temp
				elif final[1] ^ temp <= x:
					final[1] ^= temp
				else:
					final[2] ^= temp
		final = sorted(final)
		temp = temp // 2
	print(*final, sep=' ')


def powof2(n):
	ans = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			ans = i
			break
	return ans
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	result = [0] * 3
	i = powof2(n)
	while i > 0:
		difference = arr[i] - arr[0]
		if difference < 0:
			difference *= -1
			count = difference // i
			if count == 1:
				count = 2
				if result[0] ^ i <= n:
					result[0] ^= i
					count -= 1
				if count and result[1] ^ i <= n:
					result[1] ^= i
					count -= 1
				if count > 0 and result[2] ^ i <= n:
					result[2] ^= i
			elif count == 3:
				result[0] ^= i
				result[1] ^= i
				result[2] ^= i
		else:
			count = difference // i
			if count == 1:
				if result[0] ^ i <= n:
					result[0] ^= i
				elif result[1] ^ i <= n:
					result[1] ^= i
				else:
					result[2] ^= i
		result = sorted(result)
		i //= 2
	print(*result, sep=' ')


def highestpow2(n):
	ans = 0
	for i in range(n):
		if n - i & n - i - 1 == 0:
			ans = n - i
			break
	return int(ans)
for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	ans = [0, 0, 0]
	i = highestpow2(n)
	while i > 0:
		differ = x[i] - x[0]
		if differ < 0:
			differ = abs(differ)
			cnt = differ / i
			if cnt == 1:
				cnt = 2
				if ans[0] ^ i <= n:
					ans[0] ^= i
					cnt = cnt - 1
				if cnt and ans[1] ^ i <= n:
					ans[1] ^= i
					cnt = cnt - 1
				if cnt > 0 and ans[2] ^ i <= n:
					ans[2] ^= i
			elif cnt == 3:
				ans[0] ^= i
				ans[1] ^= i
				ans[2] ^= i
		else:
			cnt = differ / i
			if cnt == 1:
				if ans[0] ^ i <= n:
					ans[0] ^= i
				elif ans[1] ^ i <= n:
					ans[1] ^= i
				else:
					ans[2] ^= i
		ans = sorted(ans)
		i = int(i / 2)
	print(ans[0], ans[1], ans[2])


def pow2(n):
	res = 0
	for i in range(n):
		if n - i & n - i - 1 == 0:
			res = n - i
			break
	return int(res)
for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	ans = [0, 0, 0]
	i = pow2(n)
	while i > 0:
		dif = x[i] - x[0]
		if dif < 0:
			dif = abs(dif)
			ct = dif / i
			if ct == 1:
				ct = 2
				if ans[0] ^ i <= n:
					ans[0] ^= i
					ct = ct - 1
				if ct and ans[1] ^ i <= n:
					ans[1] ^= i
					ct = ct - 1
				if ct > 0 and ans[2] ^ i <= n:
					ans[2] ^= i
			elif ct == 3:
				ans[0] ^= i
				ans[1] ^= i
				ans[2] ^= i
		else:
			ct = dif / i
			if ct == 1:
				if ans[0] ^ i <= n:
					ans[0] ^= i
				elif ans[1] ^ i <= n:
					ans[1] ^= i
				else:
					ans[2] ^= i
		ans = sorted(ans)
		i = int(i / 2)
	print(ans[0], ans[1], ans[2])


import math

def highestPowerOf2(n):
	res = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			res = i
			break
	return res
for _ in range(int(input())):
	n = int(input())
	f = [int(i) for i in input().split()]
	ans = [0, 0, 0]
	i = highestPowerOf2(n)
	while i > 0:
		diff = f[i] - f[0]
		if diff < 0:
			diff *= -1
			c = diff // i
			if c == 1:
				c = 2
				if ans[0] ^ i <= n:
					ans[0] ^= i
					c -= 1
				if c and ans[1] ^ i <= n:
					ans[1] ^= i
					c -= 1
				if c > 0 and ans[2] ^ i <= n:
					ans[2] ^= i
			elif c == 3:
				ans[0] ^= i
				ans[1] ^= i
				ans[2] ^= i
		else:
			c = diff // i
			if c == 1:
				if ans[0] ^ i <= n:
					ans[0] ^= i
				elif ans[1] ^ i <= n:
					ans[1] ^= i
				else:
					ans[2] ^= i
		ans.sort()
		i //= 2
	print(*ans)


def cal(n) -> int:
	res = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			res = i
			break
	return res
case = int(input())
for z in range(case):
	n = int(input())
	soln = list(map(int, input().split(' ')))
	ans = [0, 0, 0]
	i = cal(n)
	while i > 0:
		dif = soln[i] - soln[0]
		if dif < 0:
			dif *= -1
			ct = dif / i
			if ct == 1:
				ct = 2
				if ans[0] ^ i <= n:
					ans[0] ^= i
					ct -= 1
				if ct and ans[1] ^ i <= n:
					ans[1] ^= i
					ct -= 1
				if ct > 0 and ans[2] ^ i <= n:
					ans[2] ^= i
			elif ct == 3:
				ans[0] ^= i
				ans[1] ^= i
				ans[2] ^= i
		else:
			ct = dif / i
			if ct == 1:
				if ans[0] ^ i <= n:
					ans[0] ^= i
				elif ans[1] ^ i <= n:
					ans[1] ^= i
				else:
					ans[2] ^= i
		i = i // 2
		ans.sort()
	print(ans[0], ans[1], ans[2])


import itertools as it
import math

def highestpowerof2(n):
	res = 0
	for i in range(n + 1)[::-1]:
		if i & i - 1 == 0:
			res = i
			break
	return res
try:
	for _ in it.repeat(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		ans = [0, 0, 0]
		i = highestpowerof2(n)
		while i > 0:
			diff = arr[i] - arr[0]
			if diff < 0:
				diff *= -1
				ct = diff // i
				if ct == 1:
					ct = 2
					if ans[0] ^ i <= n:
						ans[0] ^= i
						ct -= 1
					if ct and ans[1] ^ i <= n:
						ans[1] ^= i
						ct -= 1
					if ct > 0 and ans[2] ^ i <= n:
						ans[2] ^= i
				elif ct == 3:
					ans[0] ^= i
					ans[1] ^= i
					ans[2] ^= i
			else:
				ct = diff // i
				if ct == 1:
					if ans[0] ^ i <= n:
						ans[0] ^= i
					elif ans[1] ^ i <= n:
						ans[1] ^= i
					else:
						ans[2] ^= i
			ans = sorted(ans)
			i = i // 2
		print(ans[0], ans[1], ans[2])
except:
	pass


import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = [0, 0, 0]
	base = arr[0]
	j = math.floor(math.log2(len(arr) - 1))
	while 2 ** j >= 1:
		i = 2 ** j
		dif = arr[i] - base
		temp = []
		if dif == 3 * i:
			temp = [0, 0, 0]
		elif dif == -3 * i:
			temp = [1, 1, 1]
		elif dif == i:
			temp = [1, 0, 0]
		else:
			temp = [1, 1, 0]
		for k in range(3):
			ans[k] = ans[k] * 2 + temp[k]
		ans.sort()
		j -= 1
	print(str(' ').join(map(str, ans)))


T = int(input())

def find(v, o, j):
	if v == o:
		return -1
	elif v > o:
		if v - o == 2 ** j:
			return 1
		else:
			return 0
	elif o - v == 2 ** j:
		return 2
	else:
		return 3

def bits(N):
	i = 0
	while N >= 2 ** i:
		i += 1
	return i

def algo():
	N = int(input())
	A = list(map(int, input().split()))
	t = A[0]
	out = [0, 0, 0]
	bi = bits(N)
	for j in range(bi - 1, -1, -1):
		k = find(A[2 ** j], t, j)
		n = 0
		for i in range(k):
			while out[n] + 2 ** j > N:
				n += 1
			out[n] += 2 ** j
			n += 1
		out.sort()
	for i in out:
		print(i, end=' ')
	print()
for i in range(T):
	algo()


from math import log
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	bits = int(log(n, 2))
	x = int(2 ** bits)
	a = [0, 0, 0]
	while x > 0:
		diff = arr[x] - arr[0]
		if diff < 0:
			diff *= -1
			count = diff // x
			if count == 1:
				count = 2
				if a[0] ^ x <= n:
					a[0] ^= x
					count -= 1
				if count and a[1] ^ x <= n:
					a[1] ^= x
					count -= 1
				if count > 0 and a[2] ^ x <= n:
					a[2] ^= x
			elif count == 3:
				a[0] ^= x
				a[1] ^= x
				a[2] ^= x
		else:
			count = diff // x
			if count == 1:
				if a[0] ^ x <= n:
					a[0] ^= x
				elif a[1] ^ x <= n:
					a[1] ^= x
				else:
					a[2] ^= x
		a.sort()
		x //= 2
	print(a[0], a[1], a[2])


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	i = 2 ** int(math.log2(n))
	ans = [0, 0, 0]
	while i > 0:
		diff = arr[i] - arr[0]
		if diff < 0:
			diff = -1 * diff
			c = diff // i
			if c == 1:
				c = 2
				if ans[0] ^ i <= n:
					ans[0] = ans[0] ^ i
					c = c - 1
				if c & (ans[1] ^ i) <= n:
					ans[1] = ans[1] ^ i
					c = c - 1
				if c > 0 & ans[2] ^ i <= n:
					ans[2] = ans[2] ^ i
			elif c == 3:
				ans[0] = ans[0] ^ i
				ans[1] = ans[1] ^ i
				ans[2] = ans[2] ^ i
		else:
			c = diff // i
			if c == 1:
				if ans[0] ^ i <= n:
					ans[0] = ans[0] ^ i
				elif ans[1] ^ i <= n:
					ans[1] = ans[1] ^ i
				else:
					ans[2] = ans[2] ^ i
		ans = sorted(ans)
		i = i // 2
	b = ''
	for i in ans:
		b = b + str(i) + ' '
	print(b)


import math

def power(n):
	res = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			res = i
			break
	return res
for _ in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	i = 2 ** int(math.log2(n))
	a = [0, 0, 0]
	while i > 0:
		d = f[i] - f[0]
		if d < 0:
			d = -1 * d
			cnt = d // i
			if cnt == 1:
				cnt = 2
				if a[0] ^ i <= n:
					a[0] = a[0] ^ i
					cnt = cnt - 1
				if cnt & (a[1] ^ i) <= n:
					a[1] = a[1] ^ i
					cnt = cnt - 1
				if cnt > 0 & a[2] ^ i <= n:
					a[2] = a[2] ^ i
			elif cnt == 3:
				a[0] = a[0] ^ i
				a[1] = a[1] ^ i
				a[2] = a[2] ^ i
		else:
			cnt = d // i
			if cnt == 1:
				if a[0] ^ i <= n:
					a[0] = a[0] ^ i
				elif a[1] ^ i <= n:
					a[1] = a[1] ^ i
				else:
					a[2] = a[2] ^ i
		a = sorted(a)
		i = i // 2
	ans = ''
	for i in a:
		ans = ans + str(i) + ' '
	print(ans)


def highestPowerof2(n):
	res = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			res = i
			break
	return res
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = [0, 0, 0]
	i = highestPowerof2(n)
	while i > 0:
		diff = a[i] - a[0]
		if diff < 0:
			diff = diff * -1
			cost = diff // i
			if cost == 1:
				cost = 2
				if ans[0] ^ i <= n:
					ans[0] = ans[0] ^ i
					cost -= 1
				if cost and ans[1] ^ i <= n:
					ans[1] = ans[1] ^ i
					cost -= 1
				if cost > 0 and ans[2] ^ i <= n:
					ans[2] = ans[2] ^ i
			elif cost == 3:
				ans[0] ^= i
				ans[1] ^= i
				ans[2] ^= i
		else:
			cost = diff // i
			if cost == 1:
				if ans[0] ^ i <= n:
					ans[0] ^= i
				elif ans[1] ^ i <= n:
					ans[1] ^= i
				else:
					ans[2] ^= i
		ans.sort()
		i = i // 2
	print(f'{ans[0]} {ans[1]} {ans[2]}')


def findPowerOf2(n):
	ans = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			ans = i
			break
	return ans
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	val = [0, 0, 0]
	i = findPowerOf2(n)
	while i > 0:
		diff = arr[i] - arr[0]
		if diff < 0:
			diff *= -1
			count = diff / i
			if count == 1:
				count = 2
				if val[0] ^ i <= n:
					val[0] ^= i
					count -= 1
				if count and val[1] ^ i <= n:
					val[1] ^= i
					count -= 1
				if count > 0 and val[2] ^ i <= n:
					val[2] ^= i
			elif count == 3:
				val[0] ^= i
				val[1] ^= i
				val[2] ^= i
		else:
			count = diff // i
			if count == 1:
				if val[0] ^ i <= n:
					val[0] ^= i
				elif val[1] ^ i <= n:
					val[1] ^= i
				else:
					val[2] ^= i
		val.sort()
		i = i // 2
	print(val[0], val[1], val[2])


def solve(n):
	r = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			r = i
			break
	return r
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	p = [0, 0, 0]
	i = solve(n)
	while i > 0:
		d = a[i] - a[0]
		if d < 0:
			d *= -1
			c = int(d / i)
			if c == 1:
				c = 2
				if p[0] ^ i <= n:
					p[0] ^= i
					c -= 1
				if c and p[1] ^ i <= n:
					p[1] ^= i
					c -= 1
				if c > 0 and p[2] ^ i <= n:
					p[2] ^= i
			elif c == 3:
				p[0] ^= i
				p[1] ^= i
				p[2] ^= i
		else:
			c = int(d / i)
			if c == 1:
				if p[0] ^ i <= n:
					p[0] ^= i
				elif p[1] ^ i <= n:
					p[1] ^= i
				else:
					p[2] ^= i
		p.sort()
		i = i // 2
	print(p[0], p[1], p[2])


def deep_dive(a, b, c, bundles, base, level):
	if level == len(bundles):
		if a <= n and b <= n and (c <= n):
			return [a, b, c]
		return False
	bundle = bundles[level]
	is_success = deep_dive(a + bundle[0] * base, b + bundle[1] * base, c + bundle[2] * base, bundles, base * 2, level + 1)
	if is_success:
		return is_success
	is_success = deep_dive(a + bundle[1] * base, b + bundle[2] * base, c + bundle[0] * base, bundles, base * 2, level + 1)
	if is_success:
		return is_success
	is_success = deep_dive(a + bundle[2] * base, b + bundle[0] * base, c + bundle[1] * base, bundles, base * 2, level + 1)
	return is_success
T = int(input())
for _ in range(T):
	n = int(input())
	values = [int(x) for x in input().split()]
	two_places = [values[0]]
	jump = 1
	while jump < len(values):
		two_places.append(values[jump])
		jump = jump * 2
	(_A, _B, _C) = ([], [], [])
	for i in range(1, len(two_places)):
		change = two_places[0] - two_places[i]
		if abs(change) == 2 ** (i - 1):
			if change > 0:
				_A.append(1)
				_B.append(1)
				_C.append(0)
			else:
				_A.append(1)
				_B.append(0)
				_C.append(0)
		elif change > 0:
			_A.append(1)
			_B.append(1)
			_C.append(1)
		else:
			_A.append(0)
			_B.append(0)
			_C.append(0)
	bundles = []
	for (a, b, c) in zip(_A, _B, _C):
		bundle = (a, b, c)
		bundles.append(bundle)
	final_ans = deep_dive(0, 0, 0, bundles, 1, 0)
	print(*final_ans, sep=' ')


def isPowerofTwo(number):
	while number != 1:
		if number % 2:
			return False
		number /= 2
	return True

def hpot(n):
	res = 0
	for i in range(n, 0, -1):
		if isPowerofTwo(i):
			res = i
			break
	return res
T = int(input())
for i in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	flag = 0
	ans = [0, 0, 0]
	lis = []
	marker = 0
	maxi = 123456789
	i = hpot(N)
	mini = 0
	bool = True
	while i > 0:
		diff = arr[i] - arr[0]
		flag += 1
		if diff < 0:
			maxi = max(marker, maxi)
			diff *= -1
			marker += 2
			ct = diff // i
			if ct == 1:
				ct = 2
				mini = min(mini, flag)
				lis.append(marker)
				if ans[0] ^ i <= N:
					ans[0] ^= i
					bool = False
					ct -= 1
				if ct and ans[1] ^ i <= N:
					flag += 2
					ans[1] ^= i
					bool = True
					ct -= 1
					lis.append(marker)
				if ct > 0 and ans[2] ^ i <= N:
					ans[2] ^= i
					maxi = max(flag, marker)
					mini += 1
			elif ct == 3:
				flag += 1
				marker -= 1
				ans[0] ^= i
				check = 0
				ans[1] ^= i
				ans[2] ^= i
		else:
			ct = diff // i
			check = 1
			lis.append(mini)
			lis.append(maxi)
			if ct == 1:
				if ans[0] ^ i <= N:
					ans[0] ^= i
					bool = False
				elif ans[1] ^ i <= N:
					check += 2
					ans[1] ^= i
					bool = False
				else:
					check = 0
					lis.append(check)
					ans[2] ^= i
		ans.sort()
		i //= 2
		mini = min(flag, marker)
	print(str(ans[0]) + ' ' + str(ans[1]) + ' ' + str(ans[2]))


def isPowerofTwo(number):
	while number != 1:
		if number % 2:
			return False
		number /= 2
	return True

def hpot(n):
	res = 0
	for i in range(n, 0, -1):
		if isPowerofTwo(i):
			res = i
			break
	return res
T = int(input())
for i in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	ans = [0, 0, 0]
	i = hpot(N)
	while i > 0:
		diff = arr[i] - arr[0]
		if diff < 0:
			diff *= -1
			ct = diff // i
			if ct == 1:
				ct = 2
				if ans[0] ^ i <= N:
					ans[0] ^= i
					ct -= 1
				if ct and ans[1] ^ i <= N:
					ans[1] ^= i
					ct -= 1
				if ct > 0 and ans[2] ^ i <= N:
					ans[2] ^= i
			elif ct == 3:
				ans[0] ^= i
				ans[1] ^= i
				ans[2] ^= i
		else:
			ct = diff // i
			if ct == 1:
				if ans[0] ^ i <= N:
					ans[0] ^= i
				elif ans[1] ^ i <= N:
					ans[1] ^= i
				else:
					ans[2] ^= i
		ans.sort()
		i //= 2
	print(str(ans[0]) + ' ' + str(ans[1]) + ' ' + str(ans[2]))


def highestPowerNearN(N):
	result = 0
	for i in range(N, 1, -1):
		if i & i - 1 == 0:
			result = i
			break
	return result

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		f = list(map(int, input().split()))
		ans = [0, 0, 0]
		i = highestPowerNearN(N)
		while i > 0:
			diff = f[i] - f[0]
			if diff < 0:
				diff *= -1
				c = diff // i
				if c == 1:
					c = 2
					if ans[0] ^ i <= N:
						ans[0] ^= i
						c -= 1
					if c != 0 and ans[1] ^ i <= N:
						ans[1] ^= i
						c -= 1
					if c > 0 and ans[2] ^ i <= N:
						ans[2] ^= i
				elif c == 3:
					ans[0] ^= i
					ans[1] ^= i
					ans[2] ^= i
			else:
				c = diff // i
				if c == 1:
					if ans[0] ^ i <= N:
						ans[0] ^= i
					elif ans[1] ^ i <= N:
						ans[1] ^= i
					else:
						ans[2] ^= i
			ans.sort()
			i //= 2
		print(ans[0], ans[1], ans[2])
main()


def powerof2(n):
	res = 0
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			res = i
			return res
t = int(input())
for j in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	ans = [0] * 3
	i = powerof2(n)
	while i > 0:
		diff = arr[i] - arr[0]
		if diff < 0:
			diff = diff * -1
			ct = diff / i
			if ct == 1:
				ct = 2
				if ans[0] ^ i <= n:
					ans[0] = ans[0] ^ i
					ct -= 1
				if (ct and ans[1] ^ i) <= n:
					ans[1] = ans[1] ^ i
					ct -= 1
				if ct > 0 and ans[2] ^ i <= n:
					ans[2] = ans[2] ^ i
			elif ct == 3:
				ans[0] = ans[0] ^ i
				ans[1] = ans[1] ^ i
				ans[2] = ans[2] ^ i
		else:
			ct = diff / i
			if ct == 1:
				if ans[0] ^ i <= n:
					ans[0] = ans[0] ^ i
				elif ans[1] ^ i <= n:
					ans[1] = ans[1] ^ i
				else:
					ans[2] = ans[2] ^ i
		i = i // 2
		ans.sort()
	print(ans[0], ans[1], ans[2])


def pow(i):
	return i & i - 1 == 0
for _ in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	(a, b, c) = (0, 0, 0)
	numXbits = [(f[0] - f[i] + 3 * i) // (2 * i) if i != 0 and pow(i) else 0 for i in range(n + 1)]
	for i in range(n, -1, -1):
		if numXbits[i] == 1:
			if min(a, b, c) == a:
				a += i
			elif min(a, b, c) == b:
				b += i
			else:
				c += i
		elif numXbits[i] == 2:
			if max(a, b, c) == c:
				a += i
				b += i
			elif max(a, b, c) == a:
				b += i
				c += i
			else:
				a += i
				c += i
		elif numXbits[i] == 3:
			a += i
			b += i
			c += i
	print(a, b, c)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	ans = [0, 0, 0]
	ones = []
	i = 1
	while i <= n:
		ones.append((3 - (f[i] - f[0]) // i) // 2)
		i *= 2
	while len(ones) > 0:
		for i in range(3):
			ans[i] *= 2
		for i in range(ones[-1]):
			ans[i] += 1
		ones.pop()
		ans.sort()
	print(ans[0], ans[1], ans[2])


def high(n):
	for i in range(n, 0, -1):
		if i & i - 1 == 0:
			return i
	return 0
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = [0, 0, 0]
	i = high(n)
	while i > 0:
		dif = arr[i] - arr[0]
		if dif < 0:
			dif *= -1
			ct = dif / i
			if ct == 1:
				ct = 2
				if ans[0] ^ i <= n:
					ans[0] ^= i
					ct -= 1
				if ct and ans[1] ^ i <= n:
					ans[1] ^= i
					ct -= 1
				if ct > 0 and ans[2] ^ i <= n:
					ans[2] ^= i
			elif ct == 3:
				ans[0] ^= i
				ans[1] ^= i
				ans[2] ^= i
		else:
			ct = dif / i
			if ct == 1:
				if ans[0] ^ i <= n:
					ans[0] ^= i
				elif ans[1] ^ i <= n:
					ans[1] ^= i
				else:
					ans[2] ^= i
		ans.sort()
		i = i // 2
	print(*ans)


for test in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	if lst[0] == 0:
		print('0 0 0')
	else:
		a = lst.index(min(lst))
		lst = [lst[i] - (a ^ i) for i in range(n + 1)]
		rev = lst[::-1]
		b = n - rev.index(min(rev))
		lst = [lst[i] - (b ^ i) for i in range(n + 1)]
		c = lst.index(0)
		print(*sorted([a, b, c]), sep=' ')


from math import log2

def update_num(nums, index, n, i):
	nums[index] += i
	if nums[index] > n:
		nums[index] -= i
		return False
	return True

def update_nums(nums, n, i, x):
	if x == 1:
		if not update_num(nums, 0, n, i):
			if not update_num(nums, 1, n, i):
				update_num(nums, 2, n, i)
	if x == -1:
		if not update_num(nums, 0, n, i):
			update_num(nums, 1, n, i)
			update_num(nums, 2, n, i)
		elif not update_num(nums, 1, n, i):
			update_num(nums, 2, n, i)

def update_nums2(nums, n, i, x):
	if x == 1:
		(maxdiff, index) = (0, 0)
		for z in range(3):
			if n - nums[z] >= maxdiff:
				maxdiff = n - nums[z]
				index = z
		nums[index] += i
	if x == -1:
		(mindiff, index) = (n + 1, 0)
		for z in range(3):
			if n - nums[z] < mindiff:
				mindiff = n - nums[z]
				index = z
		for z in range(3):
			if index == z:
				continue
			nums[z] += i
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	f = list(map(int, input().split()))
	nums = [0, 0, 0]
	s = f[0]
	i = int(2 ** (log2(n) // 1))
	while i > 0:
		diff = f[i] - s
		if diff == i:
			update_nums2(nums, n, i, 1)
		elif diff == -i:
			update_nums2(nums, n, i, -1)
		elif diff == -3 * i:
			nums = [x + i for x in nums]
		i //= 2
	print(' '.join([str(x) for x in nums]))


from functools import lru_cache
import math
from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	pow = math.floor(math.log2(n))
	base = arr[0]
	op = []
	for i in range(0, pow + 1):
		pointer = 2 ** i
		if pointer > n:
			continue
		diff = (base + 3 * pointer - arr[pointer]) // (2 * pointer)
		op.append(int(diff))
	ans = []
	ret = [0, 0, 0]
	for i in range(len(op) - 1, -1, -1):
		ret.sort()
		alloc = 2 ** i
		for i in range(op[i]):
			ret[i] += alloc
	print(' '.join([str(x) for x in ret]))


def indexes(ar, n):
	ind = n
	min = ar[n]
	for i in range(n, -1, -1):
		if min > ar[i]:
			ind = i
			min = ar[i]
	return ind

def valid(ar, a, i, n):
	b_p = i ^ a
	c_p = ar[a] - i ^ a
	if max(b_p, c_p) > n:
		return False
	check = 0
	if (a ^ b_p) + (c_p ^ b_p) == ar[b_p]:
		check += 1
	if (a ^ c_p) + (c_p ^ b_p) == ar[c_p]:
		check += 1
	if check == 2:
		return True
	else:
		return False

def cal(ar, a, n):
	for i in range(ar[a] // 2 + 1):
		if valid(ar, a, i, n):
			return [i ^ a, ar[a] - i ^ a]
	return [a, a]
t = int(input())
while t > 0:
	n = int(input())
	ar = [int(i) for i in input().split(' ')]
	a = indexes(ar, n)
	ar2 = []
	for i in range(n + 1):
		ar2.append(ar[i] - a ^ i)
	ans = cal(ar, a, n)
	print(a, ans[0], ans[1])
	t -= 1


T = int(input())
import math
for test in range(T):
	n = int(input())
	F = [int(x) for x in input().split()]
	ans = [0, 0, 0]
	d = {3: 0, 1: 1, -1: 2, -3: 3}
	p = 2 ** math.floor(math.log2(n))
	while p > 0:
		for i in range(d[(F[p] - F[0]) // p]):
			ans[i] += p
		ans.sort()
		p //= 2
	for i in ans:
		print(i, end=' ')
	print()


import math
T = int(input())
for i in range(T):
	N = int(input())
	L = [int(x) for x in input().split()]
	s = int(math.log(N, 2))
	A = 0
	B = 0
	C = 0
	for j in range(s, -1, -1):
		r = 2 ** j
		diff = L[r] - L[0]
		count = 3 - (diff + 3 * r) // (2 * r)
		R = [A, B, C]
		R.sort()
		[A, B, C] = R
		if count > 0 and A + r <= N:
			count -= 1
			A = A + r
		if count > 0 and B + r <= N:
			count -= 1
			B = B + r
		if count > 0 and C + r <= N:
			count -= 1
			C = C + r
	print(A, B, C)


import math
t = int(input())
for i in range(0, t):
	n = int(input())
	inp = list(map(int, input().split(' ')))
	m = int(math.log2(n))
	arr = [0, 0, 0]
	res = []
	for p in range(0, m + 1):
		c = 2 ** (m - p)
		t = int((inp[c] - inp[0]) / c)
		if t == 3:
			pass
		elif t == 1:
			arr[0] = arr[0] + c
			for i in range(0, 2):
				for j in range(0, 2 - i):
					if arr[j] > arr[j + 1]:
						temp = arr[j]
						arr[j] = arr[j + 1]
						arr[j + 1] = temp
		elif t == -1:
			arr[0] = arr[0] + c
			arr[1] = arr[1] + c
			for i in range(0, 2):
				for j in range(0, 2 - i):
					if arr[j] > arr[j + 1]:
						temp = arr[j]
						arr[j] = arr[j + 1]
						arr[j + 1] = temp
		elif t == -3:
			arr[0] = arr[0] + c
			arr[1] = arr[1] + c
			arr[2] = arr[2] + c
	print(str(arr[0]) + ' ' + str(arr[1]) + ' ' + str(arr[2]))
	print()


for _ in range(int(input())):
	N = int(input())
	input_list = list(map(int, input().split()))
	next_idx = 1
	bits_count = {}
	for (idx, val) in enumerate(input_list):
		if idx == next_idx:
			diff = int((input_list[idx] - input_list[0]) / idx)
			if diff == -3:
				bits_count[idx] = 3
			elif diff == -1:
				bits_count[idx] = 2
			elif diff == 1:
				bits_count[idx] = 1
			next_idx = idx * 2
	total = 0
	for k in bits_count:
		if bits_count[k] == 3:
			total = total + k
	data = [total, total, total]
	for k in sorted(bits_count, reverse=True):
		if bits_count[k] == 2:
			data[0] = data[0] + k
			data[1] = data[1] + k
		elif bits_count[k] == 1:
			data[0] = data[0] + k
		data.sort()
	print(f'{data[0]} {data[1]} {data[2]}')


from random import *

def miis():
	return map(int, input().split())
for _ in range(int(input())):
	n = int(input())
	f = list(miis())
	(a, b, c) = (0, 0, 0)
	i = 1
	z = 0
	while i < n + 1:
		if (f[i] - f[0]) // i == 1:
			a += i
		elif (f[i] - f[0]) // i == -1:
			a += i
			b += i
		elif (f[i] - f[0]) // i == -3:
			a += i
			b += i
			c += i
		i *= 2
		z += 1
	abc = [a, b, c]
	while max(abc) > n:
		maxind = abc.index(max(abc))
		ind = randint(0, 2)
		while abc[ind] == abc[maxind]:
			ind = randint(0, 2)
		q = randint(0, z)
		q = 2 ** q
		if q & abc[maxind] and (not q & abc[ind]):
			abc[maxind] -= q
			abc[ind] += q
	print(*abc)


from sys import stdin
a = int(stdin.readline())
for t in range(0, a):
	b = int(stdin.readline())
	c = stdin.readline().split()
	d = [int(x) for x in c]
	start = d[0]
	f = dict()
	counter = 0
	solution = 0
	while 2 ** counter < len(d):
		f[counter] = 0
		if d[2 ** counter] - start == 2 ** counter * 3:
			f[counter] += 0
		elif d[2 ** counter] - start == 2 ** counter * 1:
			f[counter] += 1
		elif d[2 ** counter] - start == 2 ** counter * -1:
			f[counter] += 2
		elif d[2 ** counter] - start == 2 ** counter * -3:
			f[counter] += 0
			solution += 2 ** counter
		counter = counter + 1
		if 2 ** counter >= len(d):
			counter -= 1
			break
	counter2 = counter
	solution2 = solution
	while counter2 >= 0:
		if solution + 2 ** counter2 <= b and f[counter2] > 0:
			solution += 2 ** counter2
			f[counter2] -= 1
		counter2 -= 1
	counter3 = counter
	while counter3 >= 0:
		if f[counter3] == 2:
			solution2 += 2 ** counter3
			f[counter3] = 0
		counter3 -= 1
	while counter >= 0:
		if solution2 + 2 ** counter <= b and f[counter] > 0:
			solution2 += 2 ** counter
			f[counter] -= 1
		counter -= 1
	print(solution, solution2, start - solution - solution2)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	l = [0, 0, 0]
	v = 1
	dc = {}
	while v <= n:
		d = (a[v] - a[0]) // v
		d = (3 - d) // 2
		dc[v] = d
		v = v << 1
	for k in sorted(dc.keys())[::-1]:
		d = dc[k]
		for i in range(d):
			l[i] |= k
		l.sort()
	print(*l)


import math
t = int(input())
for _ in range(t):
	N = int(input())
	arr = list(map(int, input().split()))
	sum_abc = arr[0]
	A = 0
	B = 0
	C = 0
	for i in range(int(math.log(N, 2)) + 1, 0, -1):
		index = 2 ** (i - 1)
		diff = arr[index] - sum_abc
		if diff == 3 * index:
			pass
		elif diff == index:
			if A <= B and A <= C:
				A += index
			elif B <= A and B <= C:
				B += index
			else:
				C += index
		elif diff == -index:
			if A <= B and A <= C:
				A += index
				if B <= C:
					B += index
				else:
					C += index
			elif B <= A and B <= C:
				B += index
				if A <= C:
					A += index
				else:
					C += index
			else:
				C += index
				if A <= B:
					A += index
				else:
					B += index
		else:
			C += index
			B += index
			A += index
	print(A, B, C)


from bisect import bisect_left
from re import sub
import re
from typing import DefaultDict
import math
from collections import defaultdict
from math import sqrt
import collections
from sys import maxsize
from itertools import combinations_with_replacement
import sys
import copy

def sieve_erasthones(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	return prime

def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def count_factors(n):
	i = 1
	c = 0
	ans = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				c += 1
				ans.append(n // i)
			else:
				c += 2
				ans.append(i)
				ans.append(n // i)
		i += 1
	return ans
	return c

def ncr_modulo(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def isprime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return True

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n

def dict_ele_count(l):
	d = DefaultDict(lambda : 0)
	for ele in l:
		d[ele] += 1
	return d

def max_in_dict(d):
	maxi = 0
	for ele in d:
		if d[ele] > maxi:
			maxi = d[ele]
	return maxi

def element_count(s):
	l = []
	k = s[0]
	c = 0
	for ele in s:
		if ele == k:
			c += 1
		else:
			l.append([k, c])
			k = ele
			c = 1
	l.append([k, c])
	return l

def modular_exponentiation(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 != 0:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def number_of_primefactor(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def twosum(a, n, x):
	rem = []
	for i in range(x):
		rem.append(0)
	for i in range(n):
		if a[i] < x:
			rem[a[i] % x] += 1
	for i in range(1, x // 2):
		if rem[i] > 0 and rem[x - i] > 0:
			return True
	if i >= x // 2:
		if x % 2 == 0:
			if rem[x // 2] > 1:
				return True
			else:
				return False
		elif rem[x // 2] > 0 and rem[x - x // 2] > 0:
			return True
		else:
			return False

def divSum(num):
	result = 0
	i = 2
	while i <= math.sqrt(num):
		if num % i == 0:
			if i == num / i:
				result = result + i
			else:
				result = result + (i + num / i)
		i = i + 1
	return result + 1 + num

def subsequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def primeFactors(n):
	d = defaultdict(lambda : 0)
	while n % 2 == 0:
		d[2] += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			d[int(i)] += 1
			n = n / i
	if n > 2:
		d[int(n)] += 1
	return d

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	return inv * a % m

def count(n):
	ans = 0
	while n:
		ans += n % 10
		n //= 10
	return ans

def lcm(a, b):
	return a * b // math.gcd(a, b)

def check(n):
	c = 0
	while n % 2 == 0:
		n //= 2
		c += 1
	return c

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	ans = ['', '', '']
	for i in range(len(bin(n)) - 3, -1, -1):
		k = (l[2 ** i] - l[0]) // 2 ** i
		if k == 3:
			for j in range(3):
				ans[j] += '0'
		elif k == -3:
			for j in range(3):
				ans[j] += '1'
		elif k == -1:
			for j in range(2):
				ans[j] += '1'
			ans[2] += '0'
		else:
			for j in range(1, 3):
				ans[j] += '0'
			ans[0] += '1'
		ans.sort()
	for ele in ans:
		print(int(ele, 2), end=' ')
	print()
for _ in range(int(input())):
	solve()


for t in range(int(input())):
	n = int(input())
	f = list(map(int, input().split()))
	m = bin(n)
	po = len(m) - 2
	a = '0b'
	b = '0b'
	c = '0b'
	s = f[0]
	q = 2 ** (po - 1)
	saved = [False, False]
	for i in range(po):
		r = f[q] - s
		if r == 3 * q:
			a += '0'
			b += '0'
			c += '0'
		elif r == -3 * q:
			a += '1'
			b += '1'
			c += '1'
		elif r == q:
			quan = saved.count(True)
			if quan == 0:
				a += '0'
				b += '0'
				c += '1'
				saved[0] = True
				saved[1] = True
			else:
				a += '1'
				b += '0'
				c += '0'
		else:
			quan = saved.count(True)
			if quan == 0:
				a += '0'
				b += '1'
				c += '1'
				saved[0] = True
			elif quan == 1:
				a += '1'
				b += '0'
				c += '1'
				saved[1] = True
			else:
				a += '1'
				b += '1'
				c += '0'
		q //= 2
	print(int(a, 2), int(b, 2), int(c, 2))