409715: GYM103698 E Sequence
Description
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.
InputThe 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$$$.
OutputFor each test case, print a single line with the minimum sum of values.
ExampleInput4 5 2 5 1 3 2 4 5 3 5 1 3 2 4 5 25 128 31 30 28 64 1 100 1Output
5 0 148 -99Note
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.