Description

You accidentally obtained $n$ non-negative integers, where the $i$-th number is $a_i$.

Since there are too many numbers to store at home, you decide to merge them into a single number.

You can perform two types of operations:

1. Choose two numbers $x$ and $y$, then merge them into a new number $x \otimes y$.
2. Choose two numbers $x$ and $y$, then merge them into a new number $x + y$.

Here, $\otimes$ denotes the bitwise AND operation. The two numbers chosen do not need to be adjacent.

Due to certain constraints, you must use Operation 1 exactly $n-k$ times in the $n-1$ steps of merging. Your task is to maximize the final remaining number.

To help you understand the problem, here’s an example for $n=3$, $k=2$, and $a=[1, 2, 3]$:

1. Use Operation 2 to merge $1$ and $2$ into $3$. Now $a$ becomes $[3, 3]$.
2. Use Operation 1 to merge $3$ and $3$ into $3$. Now $a$ becomes $[3]$.

Input Format

Each test case contains $T$ sets of inputs.

For each test case:

• The first line contains two integers, $n$ and $k$.
• The second line contains $n$ integers, where the $i$-th integer is $a_i$.

Output Format

Output a single integer representing the answer.

3
3 2
1 2 3
4 3
2 5 6 4
5 1
1 3 7 9 11

3
12
1

Hint

• For Sample 1, the explanation is provided in the problem description.
• For Sample 2, merge $5$ and $4$ using Operation 1, then use Operation 2 for the remaining merges. It can be proven that no solution yields a result greater than $12$.
• For Sample 3, the only possible answer is merging all numbers using Operation 1.

Data Range

Here, $\operatorname{popc}(x)$ denotes the number of $1$s in the binary representation of $x$.

For all test cases:

• $1 \le T \le 10^5$,
• $1 \le k \le n \le 10^6$,
• $0 \le a_i < 2^{30}$,
• The sum of $n$ across all test cases does not exceed $2 \times 10^6$.

Special Note: For Subtask 1, $T \le 5$.

Generated by Deepseek V3.