Google OA-7 2023

Problem Description

You are given the following: Two integers N and K and an array A of size N.

Let sequence B(B_1, B_2, ..., B_2K) of size 2K is a subsequence of array A.
Let's define F(B)= (B_1 |B_2|...|B_K) ⊕ (B_(k+1) |B_(k+2)|.... |B_2K).

Where |  denotes bitwise or operation and ⊕ denotes bitwise XOR operation.

Task: Determine the maximum value of F(B) for all possible sequences B.

Note: A sequence X is a subsequence of sequence Y if X can be obtained from Y by deleting several (possibly, zero or all) elements without changing the order of the remaining elements.

Input format

The first line contains a single integer T that denotes the number of test cases. T also denotes the number of times you have to run the solve function on a different set of inputs.

For each test case:

The first line contains an integer N.

The second line contains an integer K.

The third line contains N space-separated integers denoting the array A.

Output format

For each test case in a new line, print the answer representing the maximum value of F(B) for all possible sequences B.

Constraints

1≤T≤102≤ N ≤1001 ≤ K≤ [N/2]0 ≤ A[i] <2^7

Example

N=3
K=1
A = [2, 4, 5]

Approach

There are 3 subsequences of length 2 which are as follows:
B = [2, 4] ,F(B)=2  ⊕ 4=6
B = [2, 5] ,F(B)=2  ⊕ 5=7
B = [4, 5] ,F(B)=4  ⊕ 5=1

The maximum value of F{B} is 7, thus the answer is 7.