You are given an array $a$ consisting of $n$ nonnegative integers.

Let's define the prefix OR array $b$ as the array $b_i = a_1~\mathsf{OR}~a_2~\mathsf{OR}~\dots~\mathsf{OR}~a_i$, where $\mathsf{OR}$ represents the bitwise OR operation . In other words, the array $b$ is formed by computing the $\mathsf{OR}$ of every prefix of $a$.

You are asked to rearrange the elements of the array $a$ in such a way that its prefix OR array is lexicographically maximum.

An array $x$ is lexicographically greater than an array $y$ if in the first position where $x$ and $y$ differ, $x_i > y_i$.


-----Input-----

The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ nonnegative integers $a_1, \ldots, a_n$ ($0 \leq a_i \leq 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case print $n$ integers — any rearrangement of the array $a$ that obtains the lexicographically maximum prefix OR array.


-----Examples-----

Input
5
4
1 2 4 8
7
5 1 2 3 4 5 5
2
1 101
6
2 3 4 2 3 4
8
1 4 2 3 4 5 7 1
Output
8 4 2 1 
5 2 1 3 4 5 5 
101 1 
4 3 2 2 3 4 
7 1 4 2 3 4 5 1


-----Note-----

None

Source: codeforces | Difficulty: MEDIUM
Tags: Bit manipulation

Sorting

Greedy algorithms

Complete search

Mathematics


Solutions:
MAX_BITS = 32

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

def pick_best(dec_numbers, or_prefix_dec):
	best_result = 0
	best_dec_pick = None
	best_pick_index = None
	for (index, dec_number) in dec_numbers.items():
		result = or_prefix_dec | dec_number
		if result > best_result:
			best_result = result
			best_dec_pick = dec_number
			best_pick_index = index
	return (best_dec_pick, best_pick_index)

def solve():
	t = int(input())
	for _ in range(t):
		_ = int(input())
		dec_numbers = list(map(int, input().split()))
		dec_numbers = {index: number for (index, number) in enumerate(dec_numbers)}
		ordered_numbers = list()
		or_prefix_dec = 0
		or_prefix_bin = to_bin(or_prefix_dec).zfill(MAX_BITS)
		bit_index = 0
		while bit_index < MAX_BITS:
			if or_prefix_bin[bit_index] == '1':
				bit_index += 1
				continue
			(best_dec_pick, best_pick_index) = pick_best(dec_numbers, or_prefix_dec)
			if best_pick_index is not None:
				or_prefix_dec = or_prefix_dec | best_dec_pick
				or_prefix_bin = to_bin(or_prefix_dec).zfill(MAX_BITS)
				ordered_numbers.append(best_dec_pick)
				del dec_numbers[best_pick_index]
			bit_index += 1
		ordered_numbers += list(dec_numbers.values())
		print(' '.join([str(number) for number in ordered_numbers]))
solve()


def f():
	P = int(input())
	(*a,) = map(int, input().split())
	tek = 0
	ans = []
	z = []
	b = a + []
	while b:
		c = []
		best = 0
		for i in b:
			if best == 0:
				best = i
			elif i | tek > tek and i | tek > best | tek and (best > -1):
				c += [best]
				best = i
			elif i | tek > tek and i | tek <= best | tek:
				c += [i]
			else:
				z += [i]
		b = c + []
		tek |= best
		ans += [best]
	print(*ans + z)
for i in range(int(input())):
	f()


def solve():
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		bits = 32
		mask = 0
		rearranged = []
		for i in range(bits):
			bitmask = 1 << bits - 1 - i
			if mask & bitmask:
				continue
			best = None
			for (idx, v) in enumerate(a):
				if not v & bitmask:
					continue
				if best is None:
					best = idx
					continue
				if v & (v ^ mask) > a[best] & (a[best] ^ mask):
					best = idx
			if best is not None:
				rearranged.append(a[best])
				mask |= a[best]
		for r in rearranged:
			a.remove(r)
		rearranged += a
		print(' '.join(map(str, rearranged)))
solve()


for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	pre = 0
	ans = []
	while a:
		a.sort(key=lambda x: x | pre)
		ans.append(a.pop())
		if pre == pre | ans[-1]:
			break
		pre |= ans[-1]
	print(*ans, *a)


for _ in range(int(input())):
	m = int(input())
	f = [*map(int, input().split())]
	pre = 0
	answ = []
	while f:
		f.sort(key=lambda x: x | pre)
		answ.append(f.pop())
		if pre == pre | answ[-1]:
			break
		pre |= answ[-1]
	print(*answ, *f)


import sys
read = lambda : map(int, sys.stdin.readline().split())
for _ in range(int(input())):
	n = int(input())
	nums = [*read()]
	(res, cur) = ([], 0)
	while nums:
		nums.sort(key=lambda i: i | cur)
		res.append(nums.pop())
		check = cur | res[-1]
		if check == cur:
			break
		cur = check
	print(*res, *nums)


test = int(input())
for _ in range(test):
	noice = int(input())
	asta = list(map(int, input().split()))
	asta.sort()
	(resque, curras) = ([asta[-1]], asta[-1])
	asta.pop()
	while asta:
		asta.sort(key=lambda x: x | curras)
		resque.append(asta.pop())
		if curras == resque[-1] | curras:
			break
		else:
			curras = resque[-1] | curras
	resque += asta
	print(*resque)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	diff = []
	same = []
	st = set()
	for i in range(n):
		if arr[i] in st:
			same.append(arr[i])
		else:
			diff.append(arr[i])
			st.add(arr[i])
	curr = 0
	max = 0
	max_idx = 0
	st2 = set()
	ans = []
	flag = False
	while len(st2) < len(diff):
		for i in range(len(diff)):
			if diff[i] not in st2:
				if curr | diff[i] == curr:
					st2.add(diff[i])
					same.append(diff[i])
				elif curr | diff[i] > max:
					max = curr | diff[i]
					max_idx = i
					flag = True
		curr = max
		if flag:
			ans.append(diff[max_idx])
			st2.add(diff[max_idx])
		flag = False
	main = ans + same
	print(*main)


t = int(input())

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	num = 0
	ans = []
	while arr:
		arr.sort(key=lambda x: x | num)
		ans += [arr.pop()]
		if num == num | ans[-1]:
			break
		num |= ans[-1]
	print(*ans, *arr)
while t:
	solve()
	t -= 1


import sys
R = sys.stdin.readline
for _ in range(int(R())):
	n = int(R())
	arr = [*map(int, R().split())]
	s = 0
	for m in arr:
		s |= m
	arr.sort(reverse=True)
	(temp, i) = (s - (s & arr[0]), 1)
	while temp:
		arr[i:] = sorted(arr[i:], key=lambda x: x & temp, reverse=True)
		temp -= arr[i] & temp
		i += 1
	print(*arr)


def solve(A):
	n = len(A)
	mask = 0
	res = []
	while n:
		best_i = -1
		for i in range(n):
			if best_i == -1 or A[i] | mask > A[best_i] | mask:
				best_i = i
		if mask | A[best_i] == mask:
			break
		mask |= A[best_i]
		res.append(A[best_i])
		A = A[:best_i] + A[best_i + 1:]
		n -= 1
	res.extend(A)
	return ' '.join([str(e) for e in res])

def main():
	for _ in range(int(input())):
		n = int(input())
		A = [int(e) for e in input().split()]
		print(solve(A))
main()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = []
	prefix = 0
	for i in range(32):
		f = True
		d = prefix
		idx = 0
		for j in range(len(arr)):
			if arr[j] | prefix > d:
				d = arr[j] | prefix
				f = False
				idx = j
		if f:
			ans += arr
			break
		ans.append(arr[idx])
		prefix = d
		arr.pop(idx)
	print(*ans)


f = lambda x: (31 - len(bin(int(x))[2:])) * '0' + bin(int(x))[2:]
f2 = lambda x: int(x, 2)
for cc in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ret = []
	cur = 0
	for x in range(32):
		if not arr:
			break
		mx = max(arr, key=lambda b: b | cur)
		ret.append(mx)
		arr.remove(mx)
		cur = mx | cur
	print(*ret + arr)


t = int(input())

def indx(X):
	nx = 0
	for i in range(len(X)):
		if X[i] > X[nx]:
			nx = i
	return nx
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split(' ')))
	B = A.copy()
	C = [0] * n
	D = []
	nx = indx(A)
	while A[nx] > 0:
		C[nx] = 1
		D.append(nx)
		dx = ~A[nx]
		for i in range(n):
			A[i] &= dx
		nx = indx(A)
	for i in D:
		print(B[i], end=' ')
	for i in range(n):
		if C[i] == 0:
			print(B[i], end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	arr = [*map(int, input().split())]
	curr = 0
	for j in range(31):
		arr = sorted(arr, key=lambda x: x | curr)
		x = arr.pop()
		curr |= x
		print(x, end=' ')
		if len(arr) == 0:
			break
	print(*arr)


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(a, n):
	a = sorted(a)[::-1]
	cur = 0
	ans = []
	visited = [False] * n
	for i in range(30):
		(mx, idx) = (0, -1)
		for (j, x) in enumerate(a):
			if visited[j]:
				continue
			v = cur | x
			if v > mx:
				mx = v
				idx = j
		if idx == -1:
			continue
		cur |= a[idx]
		visited[idx] = True
		ans.append(a[idx])
	for (i, x) in enumerate(a):
		if not visited[i]:
			ans.append(x)
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(' '.join((str(x) for x in solve(a, n))))


t = int(input())
for _ in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	done = [False] * n
	(res, val, idx, temp) = (0, 0, 0, 0)
	ans = []
	while not all(done):
		changed = False
		for i in range(n):
			if not done[i]:
				val = res | nums[i]
				if val > temp:
					changed = True
					temp = val
					idx = i
		if changed:
			res = temp
			ans.append(nums[idx])
			done[idx] = True
		else:
			break
	for i in range(n):
		if not done[i]:
			ans.append(nums[i])
	for i in ans:
		print(i, end=' ')
	print('')


for _ in range(int(input())):
	n = int(input())
	a = sorted([int(x) for x in input().split()])
	res = [a[-1]]
	m = a[-1]
	ans = []
	a = a[:-1]
	for j in range(0, min(31, len(a))):
		t = -1
		ind = -1
		for i in range(len(a)):
			if m | a[i] > t:
				t = m | a[i]
				ind = i
		ans.append(a[ind])
		del a[ind]
		m = t
	res.extend(ans)
	res.extend(a)
	print(*res)


tc = int(input())
for i in range(tc):
	n = int(input())
	m = list(map(int, input().split()))
	nums = list(zip(m, m))
	solution = []
	ma = max(nums)
	while ma[0] > 0:
		solution.append(ma[1])
		nums.remove(ma)
		nums = list(map(lambda p: (p[0] - (p[0] & ma[0]), p[1]), nums))
		if len(nums) == 0:
			break
		ma = max(nums)
	for num in nums:
		solution.append(num[1])
	print(*solution)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = input().split()
	for i in range(n):
		a[i] = [int(a[i]), int(a[i])]
	a.sort(reverse=True)
	ANS = 0
	b = []
	while n > 0 and a[0][0] > 0:
		b.append(a[0][1])
		ANS = ANS | a[0][0]
		a.pop(0)
		n -= 1
		for i in range(n):
			a[i][0] -= a[i][0] & ANS
		a.sort(reverse=True)
	st = str(b[0])
	for i in range(1, len(b)):
		st += ' ' + str(b[i])
	for i in range(n):
		st += ' ' + str(a[i][1])
	print(st)


for _ in range(int(input())):
	n = int(input())
	arr = [*map(int, input().split())]
	curr = 0
	for j in range(31):
		(best, z) = (-1, -1)
		for x in arr:
			y = (x | curr) ^ curr
			if y > best:
				(best, z) = (y, x)
		if best == -1:
			break
		arr.remove(z)
		print(z, end=' ')
		curr = curr | z
	print(*arr)


import sys
input = sys.stdin.readline
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	ans = [max(a)]
	done = defaultdict(lambda : 0)
	cur_or = ans[0]
	done[ans[0]] = 1
	for k in range(32):
		m = cur_or
		ele = -1
		for i in a:
			if i in done:
				continue
			new_or = cur_or | i
			if new_or > m:
				m = new_or
				ele = i
		if ele != -1:
			ans.append(ele)
			done[ele] = 1
			cur_or |= ele
	for i in a:
		if i in done and done[i] == 1:
			done[i] -= 1
			continue
		ans.append(i)
	print(*ans)