409715: GYM103698 E Sequence

Aliens have landed on earth, and you, who are studying OI, have received a problem about aliens.

You are given an array $$$a$$$ of $$$n$$$ positive integers numbered from $$$1$$$ to $$$n$$$, and a number $$$m$$$.

The value of a substring is the bitwise-OR of all its elements, minus $$$m$$$.

You want to divide the sequence into some substrings and minimize the sum of their values.

The input consists of multiple test cases. The first line contains a single integer $$$T$$$ ($$$1\le T\le 10^5$$$) — the number of test cases. Description of the test cases is as follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n\le 10^5$$$, $$$0\le m\le 10^9$$$).

The second line of each test case contains the $$$n$$$ integers of the array $$$a_1,a_2,\cdots,a_n$$$ ($$$0\le a_i\le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases is not greater that $$$5\times 10^5$$$.

For each test case, print a single line with the minimum sum of values.

4
5 2
5 1 3 2 4
5 3
5 1 3 2 4
5 25
128 31 30 28 64
1 100
1

5
0
148
-99

Subtask 1 (13 pts): $$$m=0$$$

Subtask 2 (19 pts): $$$\sum n\leq 10^2$$$

Subtask 3 (28 pts): $$$\sum n\leq 10^3$$$

Subtask 4 (40 pts): No special restrictions

For $$$100\%$$$ data, it's guaranteed $$$1\le n,T\le 10^5$$$, $$$\sum n\leq 5\times 10^5$$$, $$$0\leq a_i,m\le 10^9$$$.

• An optimal way in first case: $$$\{5,1,3,2,4\}$$$.
• An optimal way in second case: $$$\{5\},\{1\},\{3\},\{2\},\{4\}$$$.
• An optimal way in third case: $$$\{128\},\{31,30,28\},\{64\}$$$.
• An optimal way in fourth case: $$$\{1\}$$$.

Notice that the answer could be negative.