Maximum OR
Bit manipulation
Basic programming
Basics of bit manipulation
Algorithms
69.0% success
2,150 attempts
1s time
256MB memory
1024KB max code

You are given an array $$A$$ containing $$N$$ integers. You can do the following operation at most $$K$$ times:

  • Choose any index $$i$$ and increase the value of $$A_i$$ by $$1$$.

Your task is to find the maximum bitwise OR of the array.

Input format

  • The first line contains an integer $$T$$ denoting the number of test cases.
  • The first line of each test case contains two space-separated integers $$N$$ and $$K$$.
  • The second line of each test case contains $$N$$ space-separated integers denoting array $$A$$.

Output format

For each test case, print the maximum possible bitwise OR of the array after performing at most $$K$$ operations in a new line.

Constraints

\(1 \le T \le 100000\)
\(1 \le N \le 200000\)
\(0 \le K \le 1e18\)
\(0 \le A_i \le 2^{60}\)

It is guaranteed that the sum of $$N$$ over $$T$$ test cases does not exceed $$1e6$$.

Examples
Input
2
6 2
1 3 7 0 6 1
1 1000000000
0
Output
15
1000000000
Explanation

For the first testcase, we can increase the value of $$5$$-th index by $$2$$. Thus the $$A$$ becomes {\(1,3,7,0,8,1\)}. The bitwise OR of the array $$A$$ becomes $$15$$.

For the second testcase, we can increase the value of $$1$$-th index by $$1000000000$$. Thus the $$A$$ become {$$1000000000$$}. The bitwise OR of the array $$A$$ becomes $$1000000000$$.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading Editor...