Maximizing XOR After OR Operations

You are given T test cases. In each test case, you have a sequence of n non‐negative integers \(a_1,a_2,\dots,a_n\) and two parameters \(m\) and \(k\). Initially, you are also given a nonnegative integer \(m\) whose binary representation determines a set of bits that are available for use.

You can perform an arbitrary number of operations on the sequence. In each operation, you must:

• Select a nonnegative integer \(x\) such that \(x \& m = x\). (This means that every bit set in \(x\) is also set in \(m\).)
• Select an index \(i\) (\(1 \le i \le n\)) and update \(a_i \gets a_i \;|\; x\) (bitwise OR).
• Then, either update \(m \gets m - x\) or pay a cost of \(k\) (i.e. add \(k\) to your total cost \(s\)) so that \(m\) remains unchanged.

Your goal is to maximize the value

[ \Bigl(\bigoplus_{i=1}^{n}a_i\Bigr) - s, ]

where \(\bigoplus\) denotes the bitwise XOR operation, and \(s\) is the total cost paid (i.e. the sum of all \(k\)'s paid when choosing not to subtract \(x\) from \(m\)).

Note: The subtraction \(m \gets m - x\) removes from \(m\) exactly the bits used in \(x\) (since \(x\) is a submask of \(m\)). Therefore, a bit in \(m\) can be used for a subtracting (free) operation at most once. In order to use a bit more than once (if needed), you would have to pay a cost of \(k\) for that operation. Since the OR operation can only set bits (and never clear them), for each bit that is available in \(m\) you can only affect the parity of that bit in the final XOR by selecting one operation on an element which does not have that bit.

A natural strategy is as follows: For each bit \(b\) for which \(m\) has its \(b\)th bit set, look at the number of elements in the sequence that have bit \(b\) set. If the current parity for that bit (i.e. whether the count is odd or even) is not giving you a \(1\) in the final XOR and there exists at least one element without that bit (so that an OR operation will change the parity), then you can perform one operation with \(x = 2^b\) and choose the subtract option \(m \gets m - 2^b\) (which does not add to your cost) to flip the parity. Perform such operations independently for every bit that is available in \(m\) and that can be flipped. (If an operation is not possible because all elements already have the bit, you cannot change the parity.)

Compute the maximum possible value of \(\left(\bigoplus_{i=1}^{n} a_i\right) - s\) you can achieve.

inputFormat

The first line contains a single integer \(T\) (\(1 \le T \le 10^5\)) — the number of test cases.
For each test case, the first line contains three integers \(n, m, k\) (with \(0 \le m \le 10^9\) and \(0 \le k \le 10^9\)).
The second line contains \(n\) non-negative integers \(a_1, a_2, \dots, a_n\) (each \(a_i \le 10^9\)).

outputFormat

For each test case, output the maximum possible value of \(\left(\bigoplus_{i=1}^{n}a_i\right) - s\).

sample

3
2 3 5
0 0
2 3 5
1 1
3 7 1
1 2 4

3
2
7