Martian scientists explore Ganymede, one of Jupiter's numerous moons. Recently, they have found ruins of an ancient civilization. The scientists brought to Mars some tablets with writings in a language unknown to science.

They found out that the inhabitants of Ganymede used an alphabet consisting of two letters, and each word was exactly $\ell$ letters long. So, the scientists decided to write each word of this language as an integer from $0$ to $2^{\ell} - 1$ inclusively. The first letter of the alphabet corresponds to zero bit in this integer, and the second letter corresponds to one bit.

The same word may have various forms in this language. Then, you need to restore the initial form. The process of doing it is described below.

Denote the distance between two words as the amount of positions, in which these words differ. For example, the distance between $1001_2$ and $1100_2$ (in binary) is equal to two, as these words have different letters in the second and the fourth positions, counting from left to right. Further, denote the distance between words $x$ and $y$ as $d(x, y)$.

Let the word have $n$ forms, the $i$-th of which is described with an integer $x_i$. All the $x_i$ are not necessarily different, as two various forms of the word can be written the same. Consider some word $y$. Then, closeness of the word $y$ is equal to the sum of distances to each of the word forms, i. e. the sum $d(x_i, y)$ over all $1 \le i \le n$.

The initial form is the word $y$ with minimal possible nearness.

You need to help the scientists and write the program which finds the initial form of the word given all its known forms. Note that the initial form is not necessarily equal to any of the $n$ given forms.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 100$) — the number of test cases. The following are descriptions of the test cases.

The first line contains two integers $n$ and $\ell$ ($1 \le n \le 100$, $1 \le \ell \le 30$) — the amount of word forms, and the number of letters in one word.

The second line contains $n$ integers $x_i$ ($0 \le x_i \le 2^\ell - 1$) — word forms. The integers are not necessarily different.


-----Output-----

For each test, print a single integer, the initial form of the word, i. e. such $y$ ($0 \le y \le 2^\ell - 1$) that the sum $d(x_i, y)$ over all $1 \le i \le n$ is minimal possible. Note that $y$ can differ from all the integers $x_i$.

If there are multiple ways to restore the initial form, print any.


-----Examples-----

Input
7
3 5
18 9 21
3 5
18 18 18
1 1
1
5 30
1 2 3 4 5
6 10
99 35 85 46 78 55
2 1
0 1
8 8
5 16 42 15 83 65 78 42
Output
17
18
1
1
39
0
2


-----Note-----

In the first test case, the words can be written as $x_1 = 10010_2$, $x_2 = 01001_2$ and $x_3 = 10101_2$ in binary. Let $y = 10001_2$. Then, $d(x_1, y) = 2$ (the difference is in the fourth and the fifth positions), $d(x_2, y) = 2$ (the difference is in the first and the second positions), $d(x_3, y) = 1$ (the difference is in the third position). So, the closeness is $2 + 2 + 1 = 5$. It can be shown that you cannot achieve smaller closeness.

In the second test case, all the forms are equal to $18$ ($10010_2$ in binary), so the initial form is also $18$. It's easy to see that closeness is equal to zero in this case.

Source: codeforces | Difficulty: EASY
Tags: Bit manipulation

Mathematics

Greedy algorithms


Solutions:
import sys, bisect, math
from collections import deque, Counter
input = lambda : sys.stdin.readline().strip()
ceil = lambda x: math.ceil(x)
mod = 10 ** 9 + 7

def solve():
	(n, l) = map(int, input().split())
	a = list(map(lambda x: list('0' * (l - len(bin(int(x))) + 2) + bin(int(x))[2:]), input().split()))
	a = zip(*a)
	s = ''
	for i in a:
		if i.count('1') > len(i) // 2:
			s += '1'
		else:
			s += '0'
	return int(s, 2)
t = 1
t = int(input())
for _ in range(t):
	print(solve())


for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	x = a[0]
	b = []
	for i in a:
		y = bin(i)[2:]
		ans = '0' * (k - len(y)) + y
		b.append(ans)
	ans = ''
	for i in zip(*b):
		if i.count('1') > len(i) // 2:
			ans += '1'
		else:
			ans += '0'
	print(int(ans, 2))


t = int(input())
for _ in range(t):
	(n, l) = map(int, input().split())
	x = list(map(int, input().split()))
	xbin = [bin(i)[2:] for i in x]
	xbin = [(l - len(i)) * '0' + i for i in xbin]
	res = [None] * l
	for i in range(l):
		p = [item[i] == '1' for item in xbin]
		res[i] = '1' if sum(p) > n // 2 else '0'
	print(int(''.join(res), 2))


for _ in range(int(input())):
	(n, l) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr = [bin(_)[2:].zfill(l) for _ in arr]
	ans = ''
	for _ in range(l):
		temp = ''.join([i[_] for i in arr])
		if temp.count('1') > temp.count('0'):
			ans += '1'
		else:
			ans += '0'
	print(int(ans, 2))


def intlist():
	return [int(i) for i in input().split(' ')]

def stringlsit():
	return input().split(' ')

def solve():
	(n, l) = intlist()
	x = intlist()
	if n == 1:
		return x[0]
	bins = [list(bin(i)[2:]) for i in x]
	for i in range(n):
		bins[i] = (l - len(bins[i])) * ['0'] + bins[i]
	bins = list(zip(*bins))
	ans = ''
	for b in bins:
		if True:
			if b.count('1') <= n // 2:
				ans += '0'
			else:
				ans += '1'
	return int(ans, 2)
t = input()
for tt in range(int(t)):
	print(solve())


def minDistance(n, l, arr):
	count = [0 for i in range(l)]
	for num in arr:
		b = bin(num)[2:]
		diff = l - len(b)
		for i in range(diff, l):
			if b[i - diff] == '1':
				count[i] += 1
	b = ''
	for i in range(l):
		one = count[i]
		zero = n - count[i]
		if one > zero:
			b += '1'
		else:
			b += '0'
	return int(b, 2)
t = int(input())
for _ in range(t):
	(n, l) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(minDistance(n, l, arr))


import sys

def main(n, l, xs):
	s = [0] * l
	for x in xs:
		bs = bin(x)[2:].rjust(l, '0')
		for i in range(l):
			if bs[i] == '1':
				s[i] += 1
	res = ''
	for i in range(l):
		if s[i] > n >> 1:
			res += '1'
		else:
			res += '0'
	return int(res, 2)
test_case_number = int(sys.stdin.readline())
for i in range(test_case_number):
	first_line = sys.stdin.readline()
	(n, l) = first_line.split(' ')
	(n, l) = (int(n), int(l))
	second_line = sys.stdin.readline()
	xs = [int(x) for x in second_line.split(' ')]
	data = main(n, l, xs)
	sys.stdout.write(str(data) + '\n')


def ancient(n, l, array):
	y = ''
	for i in range(l):
		mask = 1 << i
		(cnt1, cnt2) = (0, 0)
		for j in range(n):
			x = array[j]
			if x & mask != 0:
				cnt1 += 1
			else:
				cnt2 += 1
		if cnt1 > cnt2:
			y = '1' + y
		else:
			y = '0' + y
	y = int(y, 2)
	print(y)
	return 1
t = int(input())
for i in range(t):
	(n, l) = map(int, input().split())
	array = list(map(int, input().split()))
	ancient(n, l, array)


from collections import Counter, deque, defaultdict
from itertools import accumulate, product, groupby
import operator
import math
from functools import reduce

def solve():
	(n, l) = [int(char) for char in input().split()]
	arr = [int(char) for char in input().split()]
	ans = ''
	for bit in range(l):
		mask = 1 << bit
		(zero, one) = (0, 0)
		for num in arr:
			if mask & num:
				one += 1
			else:
				zero += 1
		string = '0' if zero >= one else '1'
		ans = string + ans
	return int(ans, 2)
for _ in range(int(input())):
	print(solve())


for q in range(int(input())):
	(n, l) = map(int, input().split())
	arr = list(map(int, input().split()))
	binaries = []
	for i in arr:
		bina = bin(i)[2:]
		required = l - len(bina)
		bina = '0' * required + bina
		binaries.append(bina[::-1])
	ans = ''
	for i in range(0, l):
		count = 0
		for value in binaries:
			if value[i] == '1':
				count += 1
		if count > n - count:
			ans += '1'
		else:
			ans += '0'
	print(int(ans[::-1], 2))


def to_bits(l, x):
	return [1 if z == '1' else 0 for z in bin(x)[2:].zfill(l)]

def solve(n, l, x):
	y = [to_bits(l, z) for z in x]
	y = list(zip(*y))
	y = ['1' if sum(z) > n // 2 else '0' for z in y]
	y = int(''.join(y), base=2)
	return y
T = int(input())
for _ in range(T):
	(n, l) = [int(z) for z in input().split()]
	x = [int(z) for z in input().split()]
	result = solve(n, l, x)
	print(result)


t = int(input())
for _ in range(t):
	(n, l) = map(int, input().split())
	a = list(map(int, input().split()))
	ss = f'{{0:0{l}b}}'
	a = list(map(lambda x: ss.format(x), a))
	tmp = ''
	for i in range(l):
		zeros = 0
		ones = 0
		for j in range(n):
			if a[j][i] == '0':
				zeros += 1
			else:
				ones += 1
		if zeros >= ones:
			tmp += '0'
		else:
			tmp += '1'
	print(int(tmp, 2))


testcases = int(input())
for _ in range(testcases):
	(n, bit) = map(int, input().split())
	nums = list(map(int, input().split()))
	ans = ''
	for pos in range(bit):
		one_count = 0
		for num in nums:
			if num & 1 << pos > 0:
				one_count += 1
		half = n // 2
		if one_count > half:
			cur_bit = '1'
		else:
			cur_bit = '0'
		ans = cur_bit + ans
	final_ans = int(ans, 2)
	print(final_ans)


def mod(s):
	if s.count('0') >= s.count('1'):
		return '0'
	else:
		return '1'

def intToBin(a):
	return '{0:b}'.format(a)

def resize(string, leng):
	if len(string) == leng:
		return string
	else:
		return '0' * (leng - len(string)) + string

def minDist(arr, n, l):
	for i in range(n):
		arr[i] = intToBin(arr[i])
	leng = 0
	for i in range(n):
		if len(arr[i]) > leng:
			leng = len(arr[i])
	for i in range(n):
		arr[i] = resize(arr[i], leng)
	ans = ''
	for j in range(leng):
		s = ''
		for i in range(n):
			s += arr[i][j]
		ans += mod(s)
	print(int(ans, 2))
	return
for t in range(int(input())):
	(n, l) = map(int, input().split())
	arr = list(map(int, input().split()))
	minDist(arr, n, l)


t = int(input())

def to_bit(s, l):
	res = 0
	k = 0
	for ch in s[::-1]:
		if ch == '1':
			res += 2 ** (int(ch) * k)
		k += 1
	return res
for _ in range(t):
	(n, l) = map(int, input().split())
	mas = []
	te = input().split()
	for m in te:
		mas.append(format(int(m), f'0>{l}b'))
	res = ''
	for i in range(l):
		k = 0
		for p in mas:
			if p[i] == '1':
				k += 1
		if k > n / 2:
			res = res + '1'
		else:
			res = res + '0'
	print(to_bit(res, l))


from sys import exit
t = int(input())
while t:
	(n, l) = map(int, input().split())
	val = list(map(int, input('').split()))
	length = len(bin(max(val))) - 2
	val = ['{:030b}'.format(i) for i in val]
	ans = ''
	for i in range(30 - length, 30):
		(a, b) = (0, 0)
		for j in val:
			if j[i] == '0':
				a += 1
			else:
				b += 1
		if a >= b:
			ans += '0'
		else:
			ans += '1'
	print(int(ans, 2))
	t -= 1


t = int(input())
for i in range(t):
	(n, l) = map(int, input().split())
	a = [int(i) for i in input().split()]
	b = [bin(i) for i in a]
	b = [i[2:] for i in b]
	for i in range(n):
		if len(b[i]) < l:
			c = l - len(b[i])
			b[i] = '0' * c + b[i]
	s = ''
	for i in range(l):
		c = [b[j][i] for j in range(n)]
		if c.count('0') >= c.count('1'):
			s = s + '0'
		else:
			s = s + '1'
	print(int(s, 2))


for _ in range(int(input())):
	(n, l) = map(int, input().split())
	x = list(map(int, input().split()))
	i = 2 ** (l - 1)
	res = 0
	while i > 0:
		a = 0
		for j in x:
			a += 1 if j & i else 0
		res <<= 1
		res += 1 if a > n - a else 0
		i >>= 1
	print(res)


import math
t = int(input())

def getBinary(word, max_len):
	binValue = str(bin(word).split('b')[1])
	return '0' * (max_len - len(binValue)) + binValue
while t != 0:
	(n, l) = list(map(int, input().split()))
	words = list(map(int, input().split()))
	max_word = max(words)
	max_bin_len = len(bin(max_word).split('b')[1])
	bin_list = []
	for w in words:
		bin_list.append(getBinary(w, max_bin_len))
	res = ''
	for i in range(max_bin_len):
		cnt0 = 0
		for w in bin_list:
			if w[i] == '0':
				cnt0 += 1
		if cnt0 >= math.ceil(n / 2):
			res += '0'
		else:
			res += '1'
	print(int(res, 2))
	t -= 1


def get_y(li, n):
	ans = ''
	for i in range(-1, -n - 1, -1):
		count_0 = 0
		count_1 = 0
		for j in range(len(li)):
			try:
				if li[j][i] == '0':
					count_0 += 1
				else:
					count_1 += 1
			except:
				count_0 += 1
		if count_1 > count_0:
			ans = '1' + ans
		else:
			ans = '0' + ans
	return ans
t = int(input())
for _ in range(t):
	(n, l) = map(int, input().split(' '))
	x = list(map(int, input().split(' ')))
	max_len = len(bin(max(x)).replace('0b', ''))
	x = [bin(ele).replace('0b', '') for ele in x]
	y = get_y(x, max_len)
	print(int(y, 2))


def solve(word, dp):
	i = 0
	while word > 0:
		if word % 2 == 1:
			dp[i] += 1
		i += 1
		word = word // 2
	return dp

def get(val, dp, nn):
	ans = 0
	n = 1
	for i in dp:
		if i > nn // 2:
			ans += n
		n = n * 2
	return ans
t = int(input())
while t:
	t -= 1
	(n, l) = [int(i) for i in input().split()]
	dp = [0 for i in range(l)]
	arr = [int(i) for i in input().split()]
	for word in arr:
		dp = solve(word, dp)
	index = 0
	for i in range(len(dp)):
		if dp[i] != 0:
			index = i
	maxi = max(dp)
	ans = get(maxi, dp, n)
	print(ans)


from functools import reduce
for t in range(int(input())):
	(n, l) = map(int, input().split())
	forms = list(map(lambda x: bin(int(x))[2:].rjust(l, '0'), input().split()))
	answer_string = ''
	for i in range(l):
		symbols = ''.join([forms[j][i] for j in range(len(forms))])
		answer_string += str(int(symbols.count('1') > symbols.count('0')))
	print(int(answer_string, 2))


def solve(n, l, blist):
	r = ''
	for i in range(l):
		(c0, c1) = (0, 0)
		for j in range(n):
			if blist[j][i] == '0':
				c0 += 1
			else:
				c1 += 1
		if c0 >= c1:
			r += '0'
		else:
			r += '1'
	print(int(r, 2))
tc = int(input())
for _ in range(tc):
	(n, l) = map(int, input().split())
	xlist = list(map(int, input().split()))
	blist = ['{0:b}'.format(i) for i in xlist]
	blist = ['0' * abs(l - len(i)) + i if len(i) < l else i for i in blist]
	solve(n, l, blist)


import sys
input = lambda : sys.stdin.readline().rstrip()

def main():
	for _ in range(int(input())):
		(n, l) = [int(item) for item in input().split()]
		arr = [int(item) for item in input().split()]
		ans = 0
		for i in range(l):
			count = 0
			for ang in arr:
				if ang | 1 << i == ang:
					count += 1
			if count > n // 2:
				ans = ans | 1 << i
		print(ans)
main()


from math import ceil, log10
import bisect
import math
from collections import defaultdict
from itertools import groupby
from collections import defaultdict, Counter
from heapq import heappop, heappush
from collections import deque
for _ in range(int(input())):
	(n, l) = map(int, input().split())
	arr = list(map(int, input().split()))
	a = []
	for i in arr:
		k = bin(i)[2:]
		a.append(k.zfill(l))
	ans = ''
	set_bits = []
	for j in range(l):
		set_bit = 0
		for i in a:
			if i[j] == '1':
				set_bit += 1
		set_bits.append(set_bit)
	for i in set_bits:
		k = n - i
		if k >= i:
			ans += '0'
		else:
			ans += '1'
	print(int(ans, 2))


for _ in range(int(input())):
	n = int(input().split()[1])
	store = list(map(int, input().split()))
	ans = ''
	store = [bin(x)[2:].zfill(n) for x in store]
	for x in zip(*store):
		s = sum(map(int, x))
		if s * 2 > len(x):
			ans += '1'
		else:
			ans += '0'
	print(int(ans, 2))


import sys

def main():
	num_tests = int(sys.stdin.readline())
	for _ in range(num_tests):
		(num_forms, num_letters) = map(int, sys.stdin.readline().split())
		forms = [convert(int(number), num_letters) for number in sys.stdin.readline().split()]
		assert len(forms) == num_forms
		print(solve(forms, num_letters))

def convert(form, num_letters):
	return bin(form)[2:].rjust(num_letters, '0')

def solve(forms, num_letters):
	one_counts = [0] * num_letters
	zero_counts = [0] * num_letters
	for i in range(num_letters):
		for a_form in forms:
			ch = a_form[i]
			if ch == '1':
				one_counts[i] += 1
			else:
				zero_counts[i] += 1
	result = ['0'] * num_letters
	for i in range(num_letters):
		if one_counts[i] > zero_counts[i]:
			result[i] = '1'
	return int(''.join(result), 2)
main()


def solve():
	(n, length) = map(int, input().split())
	nums = map(int, input().split())
	binary = []
	for num in nums:
		b = bin(num)[2:]
		b = '0' * (length - len(b)) + b
		binary += [b]
	answer = ''
	for i in range(length):
		zeros = 0
		ones = 0
		for b in binary:
			if b[i] == '0':
				zeros += 1
			else:
				ones += 1
		if zeros >= ones:
			answer += '0'
		else:
			answer += '1'
	answer = int(answer, 2)
	print(answer)
for _ in range(int(input())):
	solve()


from collections import defaultdict

def find_form():
	(n, l) = [int(x) for x in input().split()]
	count = [defaultdict(int) for _ in range(l)]
	ans = '0b'
	words = list(input().split())
	for i in range(n):
		word = words[i]
		word = bin(int(word))[2:]
		word = (l - len(word)) * '0' + word
		for (j, letter) in enumerate(word):
			count[j][letter] += 1
	for j in range(l):
		if count[j]['0'] >= count[j]['1']:
			ans += '0'
		else:
			ans += '1'
	return ans
t = int(input())
for _ in range(t):
	print(int(find_form(), 2))


for _ in range(int(input())):
	(n, b) = map(int, input().split())
	arr = (*map(lambda x: bin(int(x))[2:].zfill(b), input().split()),)
	ans = ''
	for bit in range(b):
		if sum((num[bit] == '1' for num in arr)) > n // 2:
			ans += '1'
		else:
			ans += '0'
	print(int(ans, 2))


def solution():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [0] * k
	for x in a:
		s = bin(x)[2:][::-1]
		for i in range(len(s)):
			if s[i] == '1':
				b[i] += 1
	ans = 0
	for i in range(k):
		if b[i] * 2 > n:
			ans |= 1 << i
	print(ans)

def main():
	t = int(input())
	while t > 0:
		solution()
		t -= 1
main()


t = int(input())
for _ in range(t):
	(n, l) = map(int, input().split())
	nums = list(map(int, input().split()))
	bin_eq = []
	for i in nums:
		temp = bin(i)[2:].zfill(l)
		bin_eq.append(temp)
	ans = ''
	for i in range(l):
		z = 0
		o = 0
		for j in bin_eq:
			if j[i] == '0':
				z += 1
			else:
				o += 1
		if z >= o:
			ans += '0'
		else:
			ans += '1'
	print(int(ans, 2))


for _ in range(int(input())):
	(n, l) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(l):
		t = 0
		for j in a:
			if j & 1 << i:
				t += 1
		if t > n - t:
			ans += 1 << i
	print(ans)


t = int(input())
for _ in range(0, t):
	inputs = [int(num) for num in input().split()]
	n = inputs[0]
	l = inputs[1]
	list1 = [int(num) for num in input().split()]
	list2 = [0 for i in range(0, l)]
	for i in range(0, len(list1)):
		bini = bin(list1[i])[2:]
		k = l - 1
		for j in range(len(bini) - 1, -1, -1):
			if bini[j] == '1':
				list2[k] += 1
			k -= 1
	s = ''
	for i in range(0, len(list2)):
		if list2[i] > n / 2:
			s += '1'
		else:
			s += '0'
	print(int(s, 2))


for _ in range(int(input())):
	(n, l) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(l):
		cnt = 0
		for el in arr:
			if el & 1 << i:
				cnt += 1
		if cnt > n - cnt:
			ans += 1 << i
	print(ans)


t = int(input())
for i in range(t):
	(n, l) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	aa = 0
	p = 1
	for s in range(l):
		k = 0
		for r in a:
			if p & r != 0:
				k += 1
		if k > n // 2:
			aa += p
		p *= 2
	print(aa)


def toBin(n, base, ans):
	a = 2 ** (base - 1)
	for i in range(base):
		if n >= a:
			n -= a
			ans[i][1] += 1
		else:
			ans[i][0] += 1
		a //= 2
for t in range(int(input())):
	(n, l) = map(int, input().split())
	ans = [[0, 0] for i in range(l)]
	inp = list(map(int, input().split()))
	for n in inp:
		toBin(n, l, ans)
	s = ''
	for i in range(l):
		if ans[i][0] >= ans[i][1]:
			s += '0'
		else:
			s += '1'
	print(int(s, 2))


t = int(input())
for i in range(t):
	(n, l) = map(int, input().split())
	a = list(map(int, input().split()))
	li = [0] * 31
	for i in range(n):
		bi = bin(a[i])
		bi = bi[2:]
		bi = bi[::-1]
		le = len(bi)
		for j in range(le):
			if bi[j] == '1':
				li[j] += 1
	ans = 0
	for i in range(31):
		if n % 2 == 0:
			if li[i] > n // 2:
				ans += 2 ** i
		elif li[i] > n // 2:
			ans += 2 ** i
	print(ans)


for _ in range(int(input())):
	(n, l) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	ans = ''
	for i in range(l):
		c = 0
		for x in arr:
			if x & 1 << i != 0:
				c += 1
		if c >= n // 2 + 1:
			ans = '1' + ans
		else:
			ans = '0' + ans
	print(int(ans, 2))


T = int(input())
for testcase in range(1, T + 1):
	(n, l) = list(map(int, input().split()))
	x = list(map(int, input().split()))
	count = [0 for i in range(l)]
	for v in x:
		b = bin(v)
		j = 0
		for i in range(len(b) - 1, 1, -1):
			if b[i] == '1':
				count[j] += 1
			j += 1
	res = ''
	for i in range(l):
		if count[i] > n - count[i]:
			res = '1' + res
		else:
			res = '0' + res
	print(int(res, 2))


for _ in range(int(input())):
	(n, l) = map(int, input().split())
	l = [int(i) for i in input().split()]
	c = []
	y = 0
	ans = ''
	for i in range(33):
		y = 1 << i
		ct0 = 0
		ct1 = 0
		for k in l:
			if k & y:
				ct1 += 1
			else:
				ct0 += 1
		if ct1 > ct0:
			ans += '1'
		else:
			ans += '0'
	print(int(ans[::-1], 2))


def d(n, k):
	return '0' * (k - len(bin(n).replace('0b', ''))) + bin(n).replace('0b', '')

def O(l, p):
	x = 0
	for i in range(len(l)):
		if l[i][p] == '1':
			x = x + 1
	return x

def Z(l, p):
	x = 0
	for i in range(len(l)):
		if l[i][p] == '0':
			x = x + 1
	return x

def g(l, k):
	s = []
	x = ''
	for i in range(len(l)):
		s = s + [d(l[i], k)]
	for j in range(k):
		if O(s, j) > Z(s, j):
			x = x + '1'
		else:
			x = x + '0'
	return int(x, 2)
t = int(input())
for _ in range(t):
	(n, l) = map(int, input().split())
	q = list(map(int, input().split()))
	print(g(q, l))


t = int(input())
for _ in range(t):
	(n, l) = map(int, input().split())
	X = list(map(int, input().split()))
	if len(set(X)) == 1:
		print(X[0])
		continue
	mx = max(X)
	lmx = len(bin(mx)) - 2
	cnt = [0] * lmx
	for x in X:
		for i in range(lmx):
			if x >> i & 1 == 0:
				cnt[i] += 1
	ans = 0
	mn = n // 2 if n % 2 else n // 2 - 1
	for i in range(lmx):
		if cnt[i] <= mn:
			ans |= 1 << i
	print(ans)


def solve():
	(n, l) = map(int, input().split())
	a = list(input().split())
	for i in range(len(a)):
		a[i] = str(bin(int(a[i]))[2:]).rjust(l, '0')
	dem_0 = 0
	dem_1 = 0
	ans = []
	for i in range(l):
		dem_0 = 0
		dem_1 = 0
		for j in range(n):
			if a[j][i] == '0':
				dem_0 += 1
			else:
				dem_1 += 1
		if dem_0 >= dem_1:
			ans.append(0)
		else:
			ans.append(1)
	string = ''
	for i in ans:
		string += str(i)
	print(int(string, 2))
for i in range(int(input())):
	solve()


for _ in range(int(input())):
	(n, l) = map(int, input().split())

	def intToBin(x):
		return bin(int(x))[2:].rjust(l, '0')
	arr = list(map(intToBin, input().split()))
	finArr = []
	for i in range(l):
		s = ''
		for j in arr:
			s += j[i]
		finArr.append(s)
	ans = ''
	for i in finArr:
		ans += '1' if i.count('1') > i.count('0') else '0'
	print(int(ans, 2))


t = int(input())
ans = []
for _ in range(t):
	(n, l) = map(int, input().split())
	x = [int(i) for i in input().split()]
	res = 0
	for i in range(l):
		c1 = 0
		for w in range(n):
			c1 += x[w] % 2
			x[w] //= 2
		if c1 * 2 > n:
			res += 2 ** i
	ans.append(res)
for i in ans:
	print(i)


t = int(input())

def jj(nm):
	return bin(nm)[2:]
for i in range(t):
	(t, nfill) = list(map(int, input().split()))

	def zfl(sr: str):
		return sr.zfill(nfill)
	inp = list(map(zfl, map(jj, map(int, input().split()))))
	ans = ''
	for i in range(nfill):
		zerotime = 0
		onetime = 0
		for j in range(len(inp)):
			if inp[j][i] == '1':
				onetime += 1
			else:
				zerotime += 1
		ans += '1' if onetime > zerotime else '0'
	print(int(ans, 2))


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

def binaryToDecimal(binary):
	binary1 = binary
	(decimal, i, n) = (0, 0, 0)
	while binary != 0:
		dec = binary % 10
		decimal = decimal + dec * pow(2, i)
		binary = binary // 10
		i += 1
	return decimal
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	bits = []
	count = []
	for i in l:
		bits.append(decimalToBinary(i))
	for c in range(n):
		if len(bits[c]) != k:
			bits[c] = (k - len(bits[c])) * '0' + bits[c]
	y = 0
	count1 = 0
	count0 = 0
	for t in range(k):
		for p in range(n):
			if bits[p][t] == '1':
				count1 += 1
			else:
				count0 += 1
		if count0 >= count1:
			count.append('0')
		else:
			count.append('1')
		count1 = 0
		count0 = 0
	print(binaryToDecimal(int(''.join(count))))


t = int(input())
for i in range(0, t):
	(n, l) = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = []
	m = []
	for ele in b:
		c.append(ele)
	for ele in b:
		d = bin(ele)
		k = d[2:]
		if len(k) == l:
			m.append(k)
		else:
			while len(k) != l:
				k = '0' + k
			m.append(k)
	count = 0
	num = 0
	f = []
	n = []
	for ele in range(0, l):
		count = 0
		num = 0
		for j in m:
			if j[ele] == '0':
				count = count + 1
			else:
				num = num + 1
		if count >= num:
			f.append('0')
		else:
			f.append('1')
	j = ''
	for ele in f:
		j = j + ele
	print(int(j, 2))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l2 = []
	s = ''
	for i in l:
		l2.append(bin(i).lstrip('0b').rjust(k, '0'))
	l3 = [0] * k
	for i in l2:
		for j in range(k):
			if i[j] == '1':
				l3[j] += 1
	for i in range(k):
		m = n - l3[i]
		if m < l3[i]:
			s += '1'
		else:
			s += '0'
	print(int(s, 2))


t = int(input())

def binary(n, l):
	s = bin(n)
	s1 = s[2:]
	if len(s1) != l:
		s1 = '0' * (l - len(s1)) + s1
	return s1

def binToDeci(y, l):
	res = 0
	for i in range(l):
		res += 2 ** (l - 1 - i) * int(y[i])
	return res
for i in range(t):
	temp = [int(a) for a in input().split()]
	binArr = []
	n = temp[0]
	l = temp[1]
	y = '0' * l
	arr = [int(b) for b in input().split()]
	for c in arr:
		binArr.append(binary(c, l))
	for d in range(l):
		zeroCount = 0
		oneCount = 0
		for e in binArr:
			if e[d] == '0':
				zeroCount += 1
			else:
				oneCount += 1
		if zeroCount < oneCount:
			y = list(y)
			y[d] = '1'
			y = ''.join(y)
	print(binToDeci(y, l))


for tc in range(int(input())):
	(n, l) = map(int, input().split())
	A = list(map(int, input().split()))
	L = len(bin(max(A)).replace('0b', ''))
	Binary = []
	for i in A:
		x = bin(i).replace('0b', '')
		while len(x) != L:
			x = '0' + x
		Binary.append(x[::-1])
	res = ''
	for i in range(L):
		D = {'0': 0, '1': 0}
		for j in Binary:
			D[j[i]] += 1
		if D['0'] >= D['1']:
			res += '0'
		else:
			res += '1'
	print(int(res[::-1], 2))


for _ in range(int(input())):
	(n, o) = map(int, input().split())
	a = list(map(int, input().split()))
	b = len(bin(max(a))) - 2
	m = []
	for i in a:
		m.append(bin(i).replace('0b', '').zfill(b))
	m2 = []
	for j in range(b):
		(c0, c1) = (0, 0)
		for z in range(n):
			if m[z][j] == '1':
				c1 += 1
			else:
				c0 += 1
		if c0 >= c1:
			m2.append('0')
		else:
			m2.append('1')
	w = ''.join(m2)
	print(int(w, 2))


cases = int(input())
finalstring = ''
for case in range(cases):
	nl = [int(x) for x in input().split(' ')]
	binarynums0 = ['{0:b}'.format(int(y)) for y in input().split(' ')]
	binarynums = []
	for bin in binarynums0:
		binarynums.append('0' * (nl[1] - len(bin)) + bin)
	finalvalue = ''
	for index in range(nl[1]):
		totalOne = 0
		totalZero = 0
		for item in binarynums:
			if item[index] == '1':
				totalOne += 1
			else:
				totalZero += 1
		if totalOne > totalZero:
			finalvalue += '1'
		else:
			finalvalue += '0'
	finalvalue = str(int(finalvalue, 2))
	finalstring += finalvalue + '\n'
print(finalstring)


t = int(input())
for i in range(t):
	(n, l) = map(int, input().split())
	x = list(map(int, input().split()))
	a = []
	for j in range(n):
		y = bin(x[j])
		a.append(y.lstrip('0b'))
	m = max(x)
	b1 = bin(m)
	b2 = b1.lstrip('0b')
	l1 = len(b2)
	if len(set(x)) == 1 and x[0] == 0:
		print(0)
	else:
		for j in range(n):
			if len(a[j]) != l1:
				v = l1 - len(a[j])
				a[j] = '0' * v + a[j]
		ans = ''
		for j in range(l1):
			c1 = 0
			c2 = 0
			for k in range(n):
				if a[k][j] == '1':
					c1 = c1 + 1
				else:
					c2 = c2 + 1
			if c2 >= c1:
				ans = ans + '0'
			else:
				ans = ans + '1'
		print(int(ans, 2))


loopcount = int(input())
for loop in range(loopcount):
	y = input()
	y = y.split(' ')
	y = list(map(int, y))
	x = input()
	x = x.split(' ')
	x = list(map(int, x))
	binaryList = []
	for decimal in x:
		binary = bin(decimal).replace('0b', '')
		if len(binary) <= 0:
			binaryList.append(binary[0:y[1]])
		else:
			zero = ''
			for i in range(y[1] - len(binary)):
				zero += '0'
			binary = zero + binary
			binaryList.append(binary)
	resultbin = ''
	for i in range(y[1]):
		zero = 0
		one = 0
		for binary in binaryList:
			if binary[i] == '0':
				zero += 1
			else:
				one += 1
		if zero >= one:
			resultbin += '0'
		else:
			resultbin += '1'
	print(int(resultbin, 2))


try:
	for _ in range(int(input())):
		(n, l) = map(int, input().split())
		lst = list(map(int, input().split()))
		l = len(bin(max(lst))[2:])
		for i in range(n):
			lst[i] = bin(lst[i])[2:]
			if len(lst[i]) != l:
				h = l - len(lst[i])
				m = '0' * h
				lst[i] = m + lst[i]
		ans = [str(0) for i in range(l)]
		d = n // 2
		for i in range(l):
			count0 = 0
			count1 = 0
			for j in lst:
				if j[i] == '0':
					count0 += 1
				else:
					count1 += 1
			if count1 > d:
				ans[i] = 1
			else:
				ans[i] = 0
		p = 0
		ans.reverse()
		for i in range(l):
			if ans[i] == 1:
				p += 2 ** i
		print(p)
except:
	pass


T = int(input())
for t in range(T):
	(n, l) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	maxi = max(arr)
	tempBin = bin(maxi)[2:]
	ln = len(str(tempBin))
	temp = list()
	for i in arr:
		d2b = bin(i)[2:]
		tmpLen = len(str(d2b))
		diff = ln - tmpLen
		temp.append('0' * diff + str(d2b))
	string = ''
	tmpLen = len(temp)
	zeros = 0
	ones = 0
	for i in range(ln):
		for j in temp:
			if j[i] == '0':
				zeros += 1
			else:
				ones += 1
		if ones > zeros:
			string += '1'
		else:
			string += '0'
		zeros = 0
		ones = 0
	b = int(string, 2)
	print(b)


t = int(input())
res = []
for test in range(t):
	(n, l) = [int(x) for x in input().split()]
	nums = [int(x) for x in input().split()]
	bits = [0] * l
	for num in nums:
		temp = '{0:b}'.format(num)
		n0 = l - len(temp)
		temp = '0' * n0 + temp
		for i in range(l):
			if temp[i] == '1':
				bits[i] += 1
	ans = ''
	for i in bits:
		if i > n // 2:
			ans += '1'
		else:
			ans += '0'
	print(int(ans, 2))


def funct(n, l, words):
	result = [0] * l
	for word in words:
		word = bin(word)[2:]
		word = word[::-1]
		for (digit_idx, digit) in enumerate(word):
			result[digit_idx] += int(digit)

	def divide_and_round(x):
		x = x / n
		if x > 0.5:
			return 1
		return 0
	result = list(map(lambda a: divide_and_round(a), result[::-1]))
	return int(''.join((str(i) for i in result)), 2)
for _ in range(int(input())):
	n_and_l = input()
	(n, l) = list(map(int, n_and_l.split()))
	words = input()
	words = list(map(int, words.split()))
	print(funct(n, l, words))


import sys
t = int(sys.stdin.readline())
for i in range(t):
	(n, l) = [int(x) for x in sys.stdin.readline().split()]
	forms = [int(x) for x in sys.stdin.readline().split()]
	binary_forms = [f'{x:0{l}b}' for x in forms]
	binary_result = ''
	for j in range(l):
		zero_count = 0
		one_count = 0
		for k in range(n):
			if binary_forms[k][j] == '0':
				zero_count += 1
			else:
				one_count += 1
		binary_result += '1' if zero_count < one_count else '0'
	print(int(binary_result, 2))


def isint(n):
	return int(n) == n

def solve():
	T = int(input())
	for _ in range(T):
		(n, l) = list(map(int, input().split()))
		xs = list(map(int, input().split()))
		bxs = map(lambda x: bin(x)[2:].zfill(l), xs)
		ans = map(lambda x: '1' if sum(map(int, x)) > n / 2 else '0', list(zip(*bxs)))
		print(int(''.join(ans), base=2))
solve()


for _ in range(int(input())):
	(n, l) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [list(bin(a[i])[2:].zfill(l)) for i in range(n)]
	ans = ''
	for j in range(l):
		f = len([b[i][j] for i in range(n) if b[i][j] == '0'])
		ans += '0' if f >= n - f else '1'
	print(int(ans, 2))


for _ in range(int(input())):
	(n, l) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr = [bin(i)[2:] for i in arr]
	max_len = 0
	for i in arr:
		if len(i) > max_len:
			max_len = len(i)
	for i in range(len(arr)):
		arr[i] = '0' * (max_len - len(arr[i])) + arr[i]
	ans = 0
	for i in range(max_len):
		count1 = 0
		for j in range(n):
			if arr[j][i] == '1':
				count1 += 1
		if count1 > n - count1:
			ans = ans * 2 + 1
		else:
			ans = ans * 2
	print(ans)


for i in range(int(input())):
	(n, ll) = [int(s) for s in input().split()]
	arr = [bin(int(x))[2:].zfill(ll) for x in input().split()]
	a = ''
	for digit in range(ll):
		if sum((nn[digit] == '1' for nn in arr)) > n // 2:
			a += '1'
		else:
			a += '0'
	print(int(a, 2))


for _ in range(int(input())):
	(n, e) = map(int, input().split())
	arr = [f"{'0' * (e - len(str(bin(x))) + 2)}{str(bin(x))[2:]}" for x in map(int, input().split())]
	ans = ''
	for i in range(e):
		count_0 = count_1 = 0
		for x in arr:
			if x[i] == '0':
				count_0 += 1
			else:
				count_1 += 1
		ans += '1' if count_1 > count_0 else '0'
	print(int(ans, 2))


import io, os
import sys
for _ in range(int(input())):
	(n, l) = map(int, input().split())
	x = list(map(int, input().split()))
	ans = 0
	for i in range(l):
		cnt = 0
		for f in x:
			if f & 1 << i:
				cnt += 1
		if cnt > n - cnt:
			ans += 1 << i
	print(ans)


from collections import Counter
from math import ceil, floor, log, gcd
import bisect as bs
import sys
input = sys.stdin.readline
inp_lis = lambda : list(map(int, input().split()))
inp_multi = lambda : map(int, input().split())
inp_int = lambda : int(input().strip())

def binary(s):
	s = str(bin(s))
	s = s[2:]
	s = s[::-1]
	return s
for _ in range(int(input().strip())):
	(n, l) = inp_multi()
	x = inp_lis()
	a = [0] * l
	for each in x:
		s = binary(each)
		for i in range(len(s)):
			if s[i] == '1':
				a[i] += 1
	mid = n // 2 + 1
	ans = 0
	for (i, each) in enumerate(a):
		if each >= mid:
			ans += 2 ** i
	print(ans)


from math import floor as xx
from operator import add as XX
for _ in range(int(input())):
	(n, l) = map(int, input().split())
	(a, x, XXX) = ([0 for _ in range(l)], 0, 0)
	b = list(map(int, input().split()))
	for X in b:
		xxxx = list(map(int, bin(X)[2:].zfill(l)))
		a = list(map(XX, xxxx, a))
	a = a[::-1]
	for X in range(len(a)):
		x += pow(2, X) if a[X] > xx(n / 2) else XXX
	print(x)


def solve():
	(n, l) = list(map(int, input().split()))
	x = list(map(int, input().split()))
	ans = 0
	for i in range(l):
		one = 0
		for element in x:
			if element & 1 << i:
				one += 1
		if one > n / 2:
			ans = ans | 1 << i
	print(ans)
q = int(input())
for i in range(q):
	solve()


for _ in range(int(input())):
	(n, l) = map(int, input().split())
	x = list(map(int, input().split()))
	y = 0
	for i in range(l):
		c = 0
		for j in x:
			if j & 1 << i:
				c += 1
		if c > n - c:
			y += 1 << i
	print(y)


for _ in range(int(input())):
	(n, l) = map(int, input().split())
	x = [*map(int, input().split())]
	ans = []
	for i in range(l):
		if sum((not j & 1 << i for j in x)) < (n + 1) // 2:
			ans.insert(0, '1')
		else:
			ans.insert(0, '0')
	print(int(''.join(ans), 2))


for _ in range(int(input())):
	(n, l) = map(int, input().split(' '))
	arr = [str(bin(int(i)))[2:] for i in input().split(' ')]
	for i in range(n):
		arr[i] = '0' * (l - len(arr[i])) + arr[i]
	ans = ''
	for i in range(l):
		(z, o) = (0, 0)
		for j in range(n):
			if arr[j][i] == '0':
				z += 1
			else:
				o += 1
		ans += '1' if o > z else '0'
	print(int(ans, 2))