Tip: A brief, formal description of the problem is provided at the end of the problem statement.
City C is a city of magic, famous for its high-level mages. For a mage, the most important possession is the magic wand and the magic crystals embedded in it.
Both magic wands and magic crystals can be measured by their "magic power value." The magic power value of a magic wand is the minimum of the magic power values of all the magic crystals embedded in it.
Little $\omega$ is an apprentice mage in City C who wants to strengthen his magic wand. Before strengthening, Little $\omega$'s magic wand is embedded with $n$ magic crystals, with magic power values $a_1, a_2, \dots, a_n$ respectively.
Little $\omega$ is preparing to use a powerful secret technique to strengthen his wand. During this secret technique, he can choose any $x$, and then change the magic power value of each crystal from $a_i$ to $(a_i \oplus x)$, where $\oplus$ denotes the bitwise XOR operation. Due to Little $\omega$'s limited ability, $a_1, a_2, \dots, a_n$ and $x$ are all integers in the range $[0, 2^k - 1]$.
Little $\omega$ also discovers that this secret technique can be used for "directional strengthening." Specifically, he can spend $b_i$ stamina to perform directional strengthening on the $i$-th magic crystal, changing the magic power value that would have become $(a_i \oplus x)$ into $(a_i + x)$. Little $\omega$'s ability is limited, so the total stamina spent on directional strengthening cannot exceed $m$, and each crystal can be directionally strengthened at most once.
Little $\omega$ wants to know the maximum possible magic power value of his magic wand after strengthening, but he does not know how to calculate it, so please help him.
Formally: Given $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$, satisfying $a_i \in [0, 2^k - 1]$ and $b_i \ge 0$, you need to provide a set $S \subseteq \{1, 2, \dots, n\}$ and an $x \in [0, 2^k - 1]$ such that the following conditions are met:
- $\sum_{i \in S} b_i \le m$;
- Under the premise of satisfying the above conditions, maximize the value of $val(S, x) = \min(\min_{i \in S} (a_i + x), \min_{i \in U \setminus S} (a_i \oplus x))$.
You only need to output the maximum value of $val(S, x)$.
Input
Read from the file xor.in.
This problem contains multiple test cases. The first line contains two integers $c$ and $T$, representing the test case number and the number of test cases. The $c$ in the example indicates that the data range of that example is the same as the data range of the $c$-th test case.
Each test case is provided as follows: The first line contains three integers $n, m, k$; The second line contains $n$ integers $a_1, a_2, \dots, a_n$, representing the initial magic power values of the $n$ magic crystals; * The third line contains $n$ integers $b_1, b_2, \dots, b_n$, representing the stamina required for directional strengthening of each magic crystal.
Output
Output to the file xor.out.
For each test case, output a single line containing an integer representing the maximum magic power value Little $\omega$ can obtain for his magic wand.
Examples
Input 1
1 2 5 2 3 1 1 2 3 7 1 1 0 3 2 1 1 1 1 0
Output 1
5 2
Note 1
- For the first test case, one feasible plan is: perform directional strengthening on magic crystal 5 (i.e., $S = \{5\}$) and choose $x = 4$. The resulting magic power values of the crystals are $5, 5, 6, 7, 11$, so the magic power value of the wand is $5$. It can be proven that no better plan exists.
- For the second test case, one feasible plan is: perform directional strengthening on magic crystal 1 (i.e., $S = \{1\}$) and choose $x = 1$.
Examples 2
See the files xor/xor2.in and xor/xor2.ans in the contestant directory.
This test case satisfies $c = 4$.
Examples 3
See the files xor/xor3.in and xor/xor3.ans in the contestant directory.
This test case satisfies $c = 7$.
Examples 4
See the files xor/xor4.in and xor/xor4.ans in the contestant directory.
This test case satisfies $c = 9$.
Examples 5
See the files xor/xor5.in and xor/xor5.ans in the contestant directory.
This test case satisfies $c = 11$.
Examples 6
See the files xor/xor6.in and xor/xor6.ans in the contestant directory.
This test case satisfies $c = 14$.
Examples 7
See the files xor/xor7.in and xor/xor7.ans in the contestant directory.
This test case satisfies $c = 22$.
Subtasks
Let $\sum n$ denote the sum of $n$ over all test cases. For all test cases: $T \ge 1$; $1 \le n \le 10^5$, $1 \le \sum n \le 5 \times 10^5$; $0 \le m \le 10^9$; $0 \le k \le 120$; $\forall 1 \le i \le n$, $0 \le a_i < 2^k$; $\forall 1 \le i \le n$, $0 \le b_i \le 10^9$.
| Test Case ID | $\sum n \le$ | $n \le$ | $m \le$ | $k \le$ | Special Property |
|---|---|---|---|---|---|
| $1 \sim 3$ | $10$ | $10$ | $10^9$ | $10$ | / |
| $4 \sim 6$ | $5 \times 10^5$ | $10^5$ | $0$ | $30$ | A |
| $7, 8$ | $5 \times 10^5$ | $2$ | $10^9$ | $30$ | B |
| $9, 10$ | $5 \times 10^5$ | $10^5$ | $10^9$ | $30$ | C |
| $11 \sim 13$ | $5 \times 10^5$ | $10^5$ | $10^9$ | $30$ | C |
| $14, 15$ | $500$ | $10^2$ | $10^9$ | $30$ | / |
| $16 \sim 18$ | $5 \times 10^4$ | $10^4$ | $10^9$ | $60$ | / |
| $19 \sim 21$ | $3 \times 10^5$ | $10^5$ | $10^9$ | $120$ | / |
| $22 \sim 25$ | $5 \times 10^5$ | $10^5$ | $10^9$ | $120$ | / |
Special Property A: $m = 0$; $\forall 1 \le i \le n$, $b_i \ge 1$. Special Property B: $m = 1$; $\forall 1 \le i \le n$, $b_i \in \{1, 2\}$, and at most one $i$ satisfies $b_i = 1$. Special Property C: $m = 1$; $\forall 1 \le i \le n$, $b_i \in \{1, 2\}$.
Note
The input file for this problem is large; please use efficient input methods.
In the evaluation environment, you can use the 128-bit signed integer type __int128, which can store integers in the range $[-2^{127}, 2^{127} - 1]$. Its usage is basically the same as other integer types.
Note that this type cannot be used with standard input/output methods like cin/cout or scanf/printf. We have provided an input/output function for __int128 in the contestant directory for your use.