CF2165C Binary Wine

You are given $ n $ integers $ a_1,a_2,\ldots,a_n $ within the range $ [0,2^{30}) $ . You can spend $ 1 $ coin to increase any $ a_i $ by $ 1 $ . You can perform this operation any number of times. You need to solve $ q $ queries; for each query, you are given an integer $ c $ , also in the range $ [0,2^{30}) $ . You would like it if there exists a sequence $ b $ of length $ n $ with the following properties: - For every $ 1\le i\le n $ , $ 0\le b_i\le a_i $ . - $ b_1\oplus b_2\oplus\ldots\oplus b_n=c $ , where $ \oplus $ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). Please calculate the minimum number of coins you will have to spend, such that there exists a suitable $ b $ . The queries are independent, meaning that any operations you perform on the sequence $ a $ will not impact future queries.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case consists of two integers $ n,q $ ( $ 1\le n\le5\cdot10^5 $ , $ 1\le q\le5\cdot10^4 $ ) — the length of sequence $ a $ and the number of queries. The second line of each test case contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 0\le a_i

For each query, output a single integer — the minimum coins you will have to spend, such that there exists a suitable $ b $ .

In the first test case, we spend $ 1 $ coin to increase $ a_2 $ by $ 1 $ , resulting in sequence $ [5,8] $ . A suitable $ b $ would be $ [1,8] $ . It can be shown one cannot spend less than $ 1 $ coin to achieve the objective. In the second test case, we can spend $ 7 $ coins to increase $ a_1 $ by $ 7 $ , resulting in sequence $ [16,9,8] $ . A suitable $ b $ would be $ [16,9,1] $ .