You are given an array of $N$ integers $[A_1, A_2, \ldots, A_N]$ and an integer $K \le N$. You are going to split the array into $K$ consecutive nonempty subarrays, so that every element is included in exactly one subarray, then to find the maximum value in each subarray, and to calculate the bitwise AND
of all these maximums. What is the largest possible integer you can obtain as a result?
Input Format
- The first line contains a single integer $T$ $-$ the number of test cases. The description of test cases follows.
- The first line of each test case contains two integers $N, K$ $-$ the length of the array and the required number of subarrays.
- The second line of each test case contains $N$ integers $A_1, A_2, \ldots, A_N$.
Output Format
For each test case, output a single integer $-$ the answer to the problem.
Constraints
- $1 \le K \le N \le 200000$
- $0 \le A_i \le 10^9$
- The sum of $N$ over all test cases doesn't exceed $200000$.
Sample Input 1
3
5 1
100 10 1 1000 10000
6 2
7 8 9 10 11 12
5 3
26447356 268435455 56544987 1000000000 296823278
Sample Output 1
10000
8
52087296
Explanation
Explanation of test case 1: We need to split the array into only $1$ subarray, so the answer is just the maximum of the array.
Explanation of test case 2: One way to split the array into two parts to achieve $8$ is: $[7, 8, 9], [10, 11, 12]$. The maximums are $9$ and $12$, and their AND
is $8$.
ConversionConversion EmoticonEmoticon