D. Sum and Or
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob are playing a game on an array $$$A$$$ consisting of $$$n$$$ positive integers. Alice picks some $$$i$$$ and sets $$$A[i]$$$ to $$$A[i]$$$ $$$|$$$ $$$x$$$. Then, Bob picks some $$$j$$$ and sets $$$A[j]$$$ to $$$A[j]$$$ $$$\&$$$ $$$y$$$. Note that each player only plays one turn. The score of the game is equal to the sum of $$$A$$$.

Alice wants to minimize the score while Bob wants to maximize the score. Find the score of the game if both players play optimally.

Input

The first line of input contains the number of testcases $$$t$$$ $$$(1 \le t \le 10^3)$$$. The description of the test cases follows.

The first line of each test case contains three positive integers $$$n$$$, $$$x$$$, and $$$y$$$ $$$(1 \le n \le 10^5$$$, $$$ 1 \le x, y \le 10^9)$$$ — the size of the array $$$A$$$ and the two integers being applied to the array.

The second line of each test case contains $$$n$$$ positive integers $$$A_1, A_2, \ldots, A_n$$$ $$$(1 \le A_i \le 10^9)$$$.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-4$$$ satisfy the sum of $$$n$$$ over all test cases does not exceed $$$10^3$$$.

Tests $$$5-20$$$ satisfy the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output the score of the game if both players play optimally.

Example
Input
5
4 5 2
1 4 3 6
5 6 3
2 5 7 1 4
3 3 4
2 3 5
5 536870912 268435456
536870912 268435456 800000000 900000000 123456789
5 2 6
1 3 2 4 5
Output
14
19
9
2628763157
15
Note

In the first test case, Alice can choose $$$i = 1$$$ so that $$$A[1] = 4|5 = 5$$$ and Bob can choose $$$j = 0$$$ so that $$$A[0] = 1\&2 = 0$$$. The resulting array $$$A = \{0, 5, 3, 6\}$$$ which leads to the optimal sum of $$$14$$$.

In the second test case, an optimal solution is Alice can choose $$$i = 2$$$ so that $$$A[2] = 7|6 = 7$$$ and Bob can choose $$$j = 0$$$ so that $$$A[0] = 2\&3 = 2$$$. The resulting array $$$A = \{2, 5, 7, 1, 4\}$$$ which leads to the optimal sum of $$$19$$$.

—

Problem Idea: HaccerKat

Problem Preparation: feining_for_gm

Occurrences: Novice D