[Solution] Maximal AND solution codeforces

[Solution] Maximal AND solution codeforces – Let 𝖠𝖭𝖣AND denote the bitwise AND operation, and 𝖮𝖱OR denote the bitwise OR operation.

[Solution] Maximal AND solution codeforces

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𝑖𝑛1≤i≤n) and replace 𝑎𝑖ai with 𝑎𝑖ai 𝖮𝖱OR 2𝑗2j where 𝑗j is any integer between 00 and 3030 inclusive. In other words, in an operation you can choose an index 𝑖i (1𝑖𝑛1≤i≤n) and set the 𝑗j-th bit of 𝑎𝑖ai to 11 (0𝑗300≤j≤30).

Output the maximum possible value of 𝑎1a1 𝖠𝖭𝖣AND 𝑎2a2 𝖠𝖭𝖣AND  𝖠𝖭𝖣AND 𝑎𝑛an after performing at most 𝑘k operations.

Input

The first line of the input contains a single integer 𝑡t (1𝑡1001≤t≤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𝑛21051≤n≤2⋅1050𝑘1090≤k≤109).

Then a single line follows, containing 𝑛n integers describing the arrays 𝑎a (0𝑎𝑖<2310≤ai<231).

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 21052⋅105.

[Solution] Maximal AND solution codeforces

For each test case, output a single line containing the maximum possible 𝖠𝖭𝖣AND value of 𝑎1a1 𝖠𝖭𝖣AND 𝑎2a2 𝖠𝖭𝖣AND  𝖠𝖭𝖣AND 𝑎𝑛an after performing at most 𝑘k operations.

Example
input

Copy
4
3 2
2 1 1
7 0
4 6 6 28 6 6 12
1 30
0
4 4
3 1 3 1

[Solution] Maximal AND solution codeforces

output

Copy
2
4
2147483646
1073741825
Note

For the first test case, we can set the bit 11 (2121) of the last 22 elements using the 22 operations, thus obtaining the array [223333], which has 𝖠𝖭𝖣AND value equal to 22.

For the second test case, we can’t perform any operations so the answer is just the 𝖠𝖭𝖣AND of the whole array which is 44.

For Solution

Click here

Leave a Comment