Optimal Division

★★★★★

2 votes

, Binary Search, Algorithms

Details

Problem

You have an array $A$ of length $N$ . You have to divide the array into atmost $M$ consecutive segments such that the maximum bitwise OR of these segments is minimum.

Find the minimum possible maximum Bitwise OR of these segments if you divide optimally.

Input Format:

The first line contains an integer $T$ , denoting the number of test cases.
The first line contains two integers, $N$ and $M$ .
The next line contains $N$ space-separated integers, elements of array $A$ .

Output Format:

For each test case, print the minimum possible maximum Bitwise OR of these segments if you divide optimally.

Constraints:

$1\leq T \leq 10 \\ 1 \leq M \leq N \leq 10^5 \\ 1 \leq A[i] \leq 10^9$

Sample Input

Sample Output

4
13

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

First test case:
We can divide $A$ into $[4]$ . Bitwise OR of these segments is $4$ . Hence, the answer is $4$ , which is the minimum possible.

Second test case:
We can divide $A$ into $[12,9]$ and $[7]$ . Bitwise OR of these segments is $13,7$ . Hence, the answer is $13$ , which is the minimum possible.

Contributers:

Rohit Pradhan

Madhumeeta Bauk