Let $\mathsf{AND}$ denote the bitwise AND operation , and $\mathsf{OR}$ denote the bitwise OR operation .

You are given an array $a$ of length $n$ and a non-negative integer $k$. You can perform at most $k$ operations on the array of the following type:

Select an index $i$ ($1 \leq i \leq n$) and replace $a_i$ with $a_i$ $\mathsf{OR}$ $2^j$ where $j$ is any integer between $0$ and $30$ inclusive. In other words, in an operation you can choose an index $i$ ($1 \leq i \leq n$) and set the $j$-th bit of $a_i$ to $1$ ($0 \leq j \leq 30$).

Output the maximum possible value of $a_1$ $\mathsf{AND}$ $a_2$ $\mathsf{AND}$ $\dots$ $\mathsf{AND}$ $a_n$ after performing at most $k$ operations.


-----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 the integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le k \le 10^9$).

Then a single line follows, containing $n$ integers describing the arrays $a$ ($0 \leq a_i < 2^{31}$).

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


-----Output-----

For each test case, output a single line containing the maximum possible $\mathsf{AND}$ value of $a_1$ $\mathsf{AND}$ $a_2$ $\mathsf{AND}$ $\dots$ $\mathsf{AND}$ $a_n$ after performing at most $k$ operations.


-----Examples-----

Input
4
3 2
2 1 1
7 0
4 6 6 28 6 6 12
1 30
0
4 4
3 1 3 1
Output
2
4
2147483646
1073741825


-----Note-----

For the first test case, we can set the bit $1$ ($2^1$) of the last $2$ elements using the $2$ operations, thus obtaining the array [$2$, $3$, $3$], which has $\mathsf{AND}$ value equal to $2$.

For the second test case, we can't perform any operations so the answer is just the $\mathsf{AND}$ of the whole array which is $4$.

Source: codeforces | Difficulty: EASY
Tags: Bit manipulation

Mathematics

Greedy algorithms


Solutions:
import functools
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	r = functools.reduce(int.__and__, a)
	u = [x.count('0') for x in zip(*(f'{x:031b}' for x in a))]
	for (i, x) in enumerate(u):
		if x <= k:
			break
	else:
		print(r)
		continue
	for (i, x) in enumerate(u[i:], i):
		if x <= k:
			r |= 1 << 30 - i
			k -= x
	print(r)


from operator import iand
from functools import reduce
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	res = a[0]
	plus = 0
	u = [x.count('0') for x in zip(*(f'{x:031b}' for x in a))]
	for i in range(len(u)):
		if u[i] == 0:
			continue
		if u[i] <= k:
			plus += 2 ** (30 - i)
			k -= u[i]
	res = reduce(lambda x, y: x & y, a)
	print(res + plus)


def buh(a):
	p = str(bin(int(a)))[2:]
	return (31 - len(p)) * '0' + p

def solve(L, k, pos):
	if pos == 31:
		return 0
	c = 0
	for i in L:
		if i[pos] == '0':
			c += 1
	if c > k:
		return solve(L, k, pos + 1)
	elif c < k:
		return 2 ** (30 - pos) + solve(L, k - c, pos + 1)
	else:
		return 2 ** (30 - pos) + solve(L, 0, pos + 1)
for t in range(int(input())):
	(n, k) = map(int, input().split())
	L = list(map(buh, input().split()))
	print(solve(L, k, 0))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	ar = list(map(int, input().split()))
	if m >= 31 * n:
		print(sum((2 ** i for i in range(31))))
		continue
	kek = ar[0]
	for x in ar:
		kek &= x
	res = kek
	for i in reversed(range(31)):
		if m == 0:
			break
		q = 2 ** i
		left = sum((not x & q for x in ar))
		if m >= left > 0:
			res += q
			m -= left
	print(res)


def task(n, k, a):
	cache = []
	for i in range(0, 32):
		cache.append(0)
	for number in a:
		binary = '{0:031b}'.format(number)
		for i in range(0, 31):
			if binary[i] == '1':
				cache[30 - i] += 1
	total = 0
	for i in reversed(range(0, 31)):
		needed = n - cache[i]
		if needed <= k:
			k -= needed
			total += pow(2, i)
	print(total)
t = int(input())
for i in range(0, t):
	(n, k) = map(int, input().split())
	a = map(int, input().split())
	task(n, k, a)


def solution():
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	bits = [0] * 31
	for i in range(31):
		bits[i] = sum([j >> i & 1 == 0 for j in a])
	ans = 0
	for i in range(30, -1, -1):
		if k >= bits[i]:
			k -= bits[i]
			ans += 1 << i
	print(ans)
t = int(input())
for _ in range(t):
	solution()


def str_to_bin(s):
	b = bin(int(s))[2:]
	return '0' * (31 - len(b)) + b

def solve():
	(n, k) = map(int, input().split())
	a = list(map(str_to_bin, input().split()))
	res = 0
	for i in range(31):
		count = sum(map(lambda x: x[i] == '1', a))
		if k + count >= n:
			res += 2 ** (30 - i)
			k -= n - count
	print(res)

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for z in range(30, -1, -1):
		c = len(list(filter(lambda x: x >> z & 1 == 0, a)))
		if k >= c:
			k -= c
			ans |= 1 << z
	print(ans)


x = int(input())

def cal(m, n, arr):
	ans = arr[0]
	if m > 1:
		for i in range(1, m):
			ans = ans & arr[i]
	b = [1]
	for i in range(31):
		b.append(b[-1] * 2)
	for i in range(30, -1, -1):
		p = n
		ck = -1
		for j in range(m):
			if arr[j] & b[i] == 0:
				p -= 1
		if p >= 0:
			if p < n:
				n = p
				ans += b[i]
	return ans
for jj in range(x):
	(m, n) = [int(i) for i in input().split(' ')]
	arr = [int(i) for i in input().split(' ')]
	print(cal(m, n, arr))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	mxv = 0
	for i in range(30, -1, -1):
		cnt = sum((x & 1 << i == 0 for x in a))
		if cnt <= k:
			k -= cnt
			mxv |= 1 << i
	print(mxv)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	numbers = list(map(int, input().split()))
	binaries = []
	for item in numbers:
		u = bin(item)[2:]
		u = '0' * (31 - len(u)) + u
		binaries.append(u)
	new = ''
	for i in range(31):
		things = []
		for item in binaries:
			things.append(item[i])
		needed = things.count('0')
		if needed <= k:
			k -= needed
			new += '1'
		else:
			new += '0'
	print(int(new, 2))


def inp(*, cf=lambda x: x):
	return cf(input())

def inpint():
	return inp(cf=int)

def inp_line(*, cf=lambda x: x, s=' '):
	return list(map(cf, input().split(s)))

def inpints():
	return inp_line(cf=int)

def bitwise_and(array):
	s = array[0]
	for i in range(1, len(array)):
		s &= array[i]
	return s

def set_bit(array, b):
	for i in range(len(array)):
		array[i] = array[i] | 1 << b

def count_free_bits(x, free_bits):
	for b in range(31):
		if x & 1 << b == 0:
			free_bits[b] += 1

def test_case(case):
	(n, k) = inpints()
	free_bits = [0] * 31
	array = inp_line(cf=lambda x: count_free_bits(int(x), free_bits))
	ans = 0
	for b in reversed(range(31)):
		if free_bits[b] <= k:
			ans += 1 << b
			k -= free_bits[b]
	return ans

def main():
	T = inpint()
	for t in range(1, T + 1):
		print(test_case(t))
main()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	mxv = 0
	for i in range(30, -1, -1):
		cnt = sum((x & 1 << i == 0 for x in a))
		if cnt <= k:
			k -= cnt
			mxv |= 1 << i
	print(mxv)


def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	cnt = [0] * 31
	for x in a:
		for j in range(31):
			if x & 1 << j:
				cnt[j] += 1
	res = 0
	for j in range(30, -1, -1):
		if cnt[j] == n:
			res |= 1 << j
		elif k >= n - cnt[j]:
			k -= n - cnt[j]
			res |= 1 << j
	print(res)
t = int(input())
for _ in range(t):
	solve()


def resi():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	br = [0] * 31
	for i in range(n):
		tmp = a[i]
		for j in range(31):
			br[j] += tmp % 2
			tmp = tmp >> 1
	broj = 0
	i = 30
	while i >= 0:
		if n - br[i] <= k:
			k -= n - br[i]
			broj += 2 ** i
		i -= 1
	print(broj)
for _ in range(int(input())):
	resi()


from collections import defaultdict, deque
import math
from random import random, shuffle
from sys import setrecursionlimit
import os, sys
cwd = os.getcwd()
if os.path.exists(cwd + '/test/input.txt'):
	sys.stdin = open(cwd + '/test/input.txt', 'r')
	sys.stdout = open(cwd + '/test/output.txt', 'w')
setrecursionlimit(10 ** 6)
mi = lambda : map(int, input().split())
li = lambda : list(mi())
(dx, dy) = ([1, 1, -1, -1], [1, -1, 1, -1])
lowbit = lambda x: x & -x

class BIT:

	def __init__(self, n):
		self.bit = [0] * (n + 1)

	def upd(self, idx, val):
		bit = self.bit
		while idx <= len(bit):
			bit[idx] += val
			idx += lowbit(idx)

	def query(self, idx):
		res = 0
		bit = self.bit
		while idx > 0:
			res += bit[idx]
			idx -= lowbit(idx)
		return res

def solve():
	T = int(input())
	while T:
		T -= 1
		(n, k) = mi()
		a = li()
		cnt = [0] * 31
		for i in range(n):
			t = a[i]
			for j in range(31):
				if t >> j & 1:
					cnt[j] += 1
		res = 0
		for i in range(30, -1, -1):
			if k >= n - cnt[i]:
				k -= n - cnt[i]
				res |= 1 << i
		print(res)
solve()


bits = [2 ** i for i in range(31)]
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	strng = 0
	for i in range(30, -1, -1):
		count = 0
		for a in lst:
			if a & bits[i] == 0:
				count += 1
		if count <= k:
			strng += 2 ** i
			k -= count
	print(strng)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
t = inp()
for _ in range(t):
	(n, k) = inlt()
	a = inlt()
	ans = 0
	for j in range(30, -1, -1):
		temp = 0
		for i in a:
			if i & 1 << j == 0:
				temp += 1
		if temp <= k:
			k -= temp
			ans = ans | 1 << j
	print(ans)


def solve(nums, N, K):
	arr = [0] * 31
	for n in nums:
		i = 0
		while n:
			if n & 1:
				arr[i] += 1
			n = n >> 1
			i += 1
	ans = 0
	for i in range(30, -1, -1):
		need = N - arr[i]
		if K >= need:
			ans += 1 << i
			K -= need
	return ans
T = int(input())
for _ in range(T):
	(N, K) = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	print(solve(nums, N, K))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	lsti = []
	for j in lst:
		s = bin(j).replace('0b', '')
		l = len(s)
		s = (31 - l) * '0' + s
		lsti.append(s)
	dic = {}
	for j in range(31):
		dic[j] = 0
	for j in range(31):
		c = 0
		for g in lsti:
			if g[j] == '1':
				c += 1
		dic[j] = c
	ans = []
	ind = 0
	while True:
		if ind > 30:
			break
		else:
			co = dic[ind]
			req = n - co
			if req <= k:
				ans.append(ind)
				k -= req
			ind += 1
	c = 0
	for h in ans:
		c += 2 ** (31 - h - 1)
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	temp = ['{0:032b}'.format(i) for i in a]
	ans = ''
	for dig in range(1, 32):
		flag = True
		count = 0
		for j in temp:
			if j[dig] == '1':
				pass
			else:
				count += 1
				flag = False
		if count <= k:
			ans += '1'
			k -= count
		else:
			ans += '0'
	print(int(ans, 2))


import sys
import collections
from math import ceil, gcd, sqrt, log
import bisect
INF = float('inf')
mod = 1000000007

def solve():
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	net = [0] * 31
	for x in A:
		for i in range(31):
			if x & 1 << 30 - i:
				net[i] += 1
	final_mask = []
	for i in net:
		if n - i > k:
			final_mask.append(0)
			continue
		k -= n - i
		final_mask.append(1)
	ans = ''
	for i in final_mask:
		if i == 1:
			ans += '1'
		else:
			ans += '0'
	print(int(ans, 2))
t = int(input())
while t != 0:
	solve()
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [n] * 31
	for i in range(31):
		mask = 1 << i
		for v in a:
			if v & mask != 0:
				b[i] -= 1
	ans = 0
	for i in range(30, -1, -1):
		if b[i] <= k:
			k -= b[i]
			b[i] = 0
		if b[i] == 0:
			ans += 1 << i
	print(ans)


T = int(input())
for _ in range(T):
	(N, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	cnt = [0] * 31
	for n in arr:
		s = str(bin(n))
		s = s[:1:-1]
		for i in range(len(s)):
			if s[i] == '1':
				cnt[i] += 1
	ans = 0
	for i in range(len(cnt) - 1, -1, -1):
		if k >= N - cnt[i]:
			k -= N - cnt[i]
			ans += 1 << i
	print(ans)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = []
	for i in l:
		l1.append('{:032b}'.format(i))
	arr = []
	ind = []
	for i in range(32):
		arr.append(0)
	for i in l1:
		for j in range(32):
			if i[j] == '1':
				arr[j] += 1
	for i in range(1, 32):
		if n - arr[i] <= k:
			k -= n - arr[i]
			arr[i] += n - arr[i]
	for i in range(1, 32):
		if arr[i] == n:
			ind.append(32 - i - 1)
	ans = 0
	for i in ind:
		ans += 2 ** i
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	bineries = list(map(int, 31 * '0'))
	for num in a:
		b = bin(num)[2:][::-1]
		for k1 in range(len(b)):
			if b[k1] == '1':
				bineries[30 - k1] += 1
	result = '0b'
	for j in range(31):
		if n - bineries[j] <= k and k > 0:
			k -= n - bineries[j]
			result += '1'
		else:
			result += str(int(bineries[j] == n))
	print(int(result, 2))


import math
from collections import defaultdict
t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	lis = list(map(int, input().split()))
	ans = 0
	for j in range(30, -1, -1):
		tot = 0
		for y in lis:
			if y >> j & 1 == 0:
				tot += 1
		if tot == 0:
			ans = ans + 2 ** j
		elif tot <= k:
			ans = ans + 2 ** j
			k = k - tot
	print(ans)


import sys
input = sys.stdin.readline

def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	d = {i: n for i in range(31)}
	for x in a:
		for i in range(31):
			d[i] -= x & 1 << i != 0
	ans = 0
	for i in range(30, -1, -1):
		if d[i] <= k:
			ans += 1 << i
			k -= d[i]
	print(ans)
tst = int(input())
for tt in range(tst):
	solve()


NUM_BITS = 31
t = int(input())
for _ in range(t):
	(n, k) = tuple(map(int, input().split()))
	a = tuple(map(int, input().split()))
	histogram = [0] * NUM_BITS
	mask = 1
	for i in range(NUM_BITS):
		for num in a:
			histogram[i] += num & mask != 0
		mask <<= 1
	max_and = 0
	mask = 1 << NUM_BITS - 1
	for i in range(NUM_BITS - 1, -1, -1):
		if n - histogram[i] <= k:
			k -= n - histogram[i]
			max_and |= mask
		mask >>= 1
	print(max_and)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr = ['{0:031b}'.format(i) for i in arr]
	counts = [n] * 31
	for i in arr:
		for j in range(31):
			if i[j] == '1':
				counts[j] -= 1
	l = 0
	while l < 31:
		if counts[l] <= k:
			k -= counts[l]
			counts[l] = 0
		l += 1
	ans = 0
	for i in range(30, -1, -1):
		if counts[30 - i] == 0:
			ans += 2 ** i
	print(ans)


for test in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [n] * 31
	ans = 0
	for i in range(31)[::-1]:
		p = 2 ** i
		for el in a:
			if el & p:
				b[i] -= 1
		if k >= b[i]:
			k -= b[i]
			ans += p
	print(ans)


a = int(input())
for x in range(a):
	(b, c) = map(int, input().split())
	j = list(map(int, input().split()))
	l = [0 for x in range(31)]
	for y in range(b):
		s = format(j[y], '031b')
		for z in range(31):
			if s[z] == '1':
				l[z] += 1
	for y in range(31):
		if b - l[y] <= c:
			c -= b - l[y]
			l[y] = b
	s = 30
	ans = 0
	for y in range(31):
		if l[y] == b:
			ans += 2 ** s
		s -= 1
	print(ans)


bin_func = [1]
for m in range(1, 31):
	bin_func.append(bin_func[-1] * 2)
bin_func.reverse()

def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	res = 0
	for i in range(31):
		count = sum(map(lambda x: x & bin_func[i] == bin_func[i], a))
		if k + count >= n:
			res += bin_func[i]
			k -= n - count
	print(res)

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


def bin_dec(arr):
	c = 0
	ans = 0
	for i in range(31, -1, -1):
		ans += 2 ** c * arr[i]
		c += 1
	return ans

def bit(n, arr):
	c = 0
	while n > 0:
		a = n & 1
		if a == 1:
			arr[c] += 1
		c += 1
		n >>= 1
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	li = [0 for i in range(32)]
	for ele in arr:
		bit(ele, li)
	p = 0
	ans = []
	for i in range(31, -1, -1):
		if li[i] == n:
			ans.append(1)
		elif li[i] + k >= n and i <= 30:
			ans.append(1)
			k -= n - li[i]
		else:
			ans.append(0)
	ans = bin_dec(ans)
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	cnt = [0] * 31
	for item in a:
		b = str(bin(item))[2:][::-1]
		for i in range(len(b)):
			if b[i] == '1':
				cnt[i] += 1
	for i in range(30, -1, -1):
		if n - cnt[i] <= k:
			k -= n - cnt[i]
			cnt[i] = n
	res = 0
	for i in range(31):
		if cnt[i] == n:
			res += 2 ** i
	print(res)


def bin(n):
	i = 1 << 30
	ind = 0
	while i > 0:
		if n & i != 0:
			output[ind] += 1
		i = i // 2
		ind += 1
	return output
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	output = [0] * 31
	for item in arr:
		bin(item)
	ind = 0
	while ind < 31:
		diff = n - output[ind]
		if k >= diff:
			k = k - diff
			output[ind] = n
		ind += 1
	ans = 0
	for (ind, val) in enumerate(output):
		if val == n:
			ans += 1 << 30 - ind
	print(ans)


import math

def solve():
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	bits = [0 for i in range(31)]
	for num in arr:
		x = 0
		while num > 0:
			bits[x] += num & 1
			num = num >> 1
			x += 1
	for i in range(30, -1, -1):
		if n - bits[i] <= k:
			k -= n - bits[i]
			bits[i] = n
	ans = 0
	for i in range(31):
		if bits[i] >= n:
			ans += pow(2, i)
	print(ans)
t = int(input())
for i in range(t):
	solve()


def main():
	t = int(input())
	while t:
		t -= 1
		(n, k) = list(map(int, input().split()))
		arr = list(map(int, input().split()))
		cnt = [0 for _ in range(31)]
		for i in range(n):
			for j in range(30, -1, -1):
				if arr[i] & 1 << j:
					cnt[j] += 1
		ans = 0
		for j in range(30, -1, -1):
			need = n - cnt[j]
			if need <= k:
				k -= need
				ans += 1 << j
		print(ans)
main()


from collections import defaultdict
from functools import lru_cache
import heapq
from locale import resetlocale
import sys
import random

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return s

def invr():
	return map(int, input().split())
T = inp()

def solve():
	(n, k) = invr()
	nums = inlt()
	jl = [0] * 31
	for i in range(n):
		for j in range(31):
			jl[j] += 1 if nums[i] & 1 << j else 0
	ans = 0
	for j in range(30, -1, -1):
		if jl[j] == n:
			ans += 2 ** j
		elif jl[j] + k >= n:
			ans += 2 ** j
			k -= n - jl[j]
	print(ans)
for _ in range(T):
	solve()


def solve():
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	bits = [0 for i in range(31)]
	for num in arr:
		x = 0
		while num > 0:
			bits[x] += num & 1
			num >>= 1
			x += 1
	for i in range(30, -1, -1):
		if n - bits[i] <= k:
			k -= n - bits[i]
			bits[i] = n
	ans = 0
	for i in range(31):
		if bits[i] >= n:
			ans += 1 << i
	print(ans)
t = int(input())
for _ in range(t):
	solve()


for i in range(int(input())):
	(n, k) = map(int, input().split())
	nums = list(map(int, input().split()))
	ans = 0
	bitmap = [0] * 31
	for p in range(0, 31):
		for m in nums:
			if m & 1 << p == 0:
				bitmap[p] += 1
	for g in range(30, -1, -1):
		if k >= bitmap[g]:
			k -= bitmap[g]
			ans += 1 << g
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	arr = [0 for i in range(31)]
	for i in range(n):
		x = bin(a[i])
		x = str(x)
		x = x[2:]
		x = x[::-1]
		n2 = len(x)
		for j in range(n2):
			if x[j] == '1':
				arr[j] += 1
	arr.reverse()
	ans = 0
	for i in range(31):
		if n - arr[i] <= k:
			k = k - (n - arr[i])
			ans = ans + 2 ** (30 - i)
	print(ans)


def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	bit_counts = [0] * 31
	for x in a:
		x_bin = bin(x)[2:]
		for (index, bit) in enumerate(x_bin[::-1]):
			bit_counts[index] += int(bit)
	res = []
	for bit_cnt in bit_counts[::-1]:
		if k + bit_cnt >= n:
			res.append('1')
			k -= n - bit_cnt
		else:
			res.append('0')
	print(int(''.join(res), 2))

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(30, -1, -1):
		unset = 0
		for j in a:
			if j & 1 << i == 0:
				unset += 1
		if unset <= k:
			k -= unset
			ans += 2 ** i
	print(ans)


for _ in range(int(input())):
	(N, K) = list(map(int, input().split(' ')))
	A = list(map(int, input().split(' ')))
	ans = 0
	for i in range(30, -1, -1):
		unset = 0
		for j in A:
			unset += j & 1 << i == 0
		if unset <= K:
			K -= unset
			ans |= 1 << i
	print(ans)


def main():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	st = 2 ** 30
	ans = 0
	for i in range(30, -1, -1):
		c = 0
		for j in range(len(a)):
			if a[j] % (st * 2) < st:
				c += 1
		if c <= k:
			k -= c
			ans += st
		st //= 2
	print(ans)
for i in range(int(input())):
	main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	count = [0 for _ in range(31)]
	powers = [2 ** i for i in range(31)]
	for num in arr:
		for i in range(31):
			if powers[i] & num:
				count[i] += 1
	ind = 30
	while k and ind >= 0:
		if k >= n - count[ind]:
			k -= n - count[ind]
			count[ind] = n
		ind -= 1
	ans = 0
	for i in range(31):
		if count[i] == n:
			ans += powers[i]
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	for i in range(len(a)):
		a[i] = bin(a[i])[2:]
		if len(a[i]) < 31:
			a[i] = '0' * (31 - len(a[i])) + a[i]
	oneTotals = [0 for i in range(31)]
	for i in range(31):
		total = 0
		for j in range(len(a)):
			if a[j][i] == '1':
				total += 1
		oneTotals[i] = total
	ans = ['0' for i in range(31)]
	for i in range(31):
		if n - oneTotals[i] <= k:
			k -= n - oneTotals[i]
			ans[i] = '1'
	ans = ''.join(ans)
	ans = int(ans, 2)
	print(ans)


def make_list(a):
	bit_list = [0] * 31
	for num in a:
		count = 1
		while num > 0:
			bit_list[31 - count] += num % 2
			num = num // 2
			count += 1
	return bit_list

def test_case(a, k):
	max_add = len(a)
	ans = 0
	for (idx, place) in enumerate(make_list(a)):
		if max_add - place > k:
			continue
		ans += 2 ** (30 - idx)
		k -= max_add - place
	print(ans)
for _ in range(int(input())):
	n = int(input().split(' ')[1])
	numbers = [int(k) for k in input().split(' ')]
	test_case(numbers, n)


import sys
import math
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
t = inp()
for test in range(t):
	(n, k) = invr()
	a = inlt()
	count_ones = [0 for i in range(31)]
	res = 0
	for val in a:
		for j in range(30, -1, -1):
			if val & 1 << j:
				count_ones[j] += 1
	for j in range(30, -1, -1):
		if k + count_ones[j] >= n:
			k -= n - count_ones[j]
			res += 1 << j
	print(res)


z = int(input())
for i in range(z):
	(n, k) = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	l_dic = []
	for i in range(31):
		l_dic.append({0: 0})
	for j in range(n):
		int_number = l[j]
		bin_number = bin(l[j])
		n_bin = len(bin_number) - 2
		n_dicider = 31 - n_bin
		for t in range(0, n_dicider):
			l_dic[t][0] += 1
		for s in range(n_dicider, 31):
			if bin_number[s - n_dicider + 2] == '0':
				l_dic[s][0] += 1
	ans = 0
	u = 0
	while u < 31:
		if l_dic[u][0] <= k:
			ans = ans + 2 ** (31 - u - 1)
			k -= l_dic[u][0]
		elif l_dic[u][0] == 0:
			ans = ans + 2 ** (31 - u - 1)
		u += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	buckets = [0 for _ in range(31)]
	for i in range(31):
		for v in a:
			if v & 1 << i:
				buckets[i] += 1
	i = 30
	out = 0
	while i >= 0 and k:
		if buckets[i] + k >= n:
			k -= n - buckets[i]
			buckets[i] = n
		i -= 1
	for i in range(31):
		if buckets[i] == n:
			out |= 1 << i
	print(out)


def countt(ind, a):
	s = 0
	for el in a:
		s += int(el[ind])
	return s
t = int(input())
for qwer in range(t):
	(n, k) = map(int, input().split())
	sp = list(map(int, input().split()))
	cop = sp.copy()
	prib = list('0000000000000000000000000000000')
	for i in range(n):
		sp[i] = bin(sp[i])[2:].zfill(31)
	for i in range(31):
		f = countt(i, sp)
		if n - f <= k:
			k -= n - f
			prib[i] = '1'
		if k <= 0:
			break
	g = cop[0]
	for i in range(1, n):
		g = g & cop[i]
	otv = int(''.join(prib), 2) | g
	print(otv)


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