CF2147E Maximum OR Popcount

You are given an array of $ n $ non-negative integers. You want to answer given $ q $ independent scenarios. In the $ i $ -th scenario, you are allowed to perform the following operation at most $ b_i $ times: - Choose an element of the array and increase it by $ 1 $ . Your goal is to maximize the number of bits that are equal to $ 1 $ in the [bitwise OR](https://en.wikipedia.org/wiki/Bitwise_operation#OR) of all numbers in the array. Find this number for each scenario.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^3 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ q $ ( $ 1 \leq n, q \leq 10^{5} $ ) — the size of the array and the number of scenarios. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \leq a_i \leq 10^{9} $ ) — the elements of the array. The $ i $ -th of the next $ q $ lines contains a single integer $ b_i $ ( $ 0 \leq b_i \leq 10^{9} $ ) — the maximum number of operations allowed in the $ i $ -th scenario. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^{5} $ , and the sum of $ q $ over all test cases does not exceed $ 10^{5} $ .

For each test case, output $ q $ lines, the $ i $ -th of them containing a single integer — the maximum possible number of bits equal to $ 1 $ in the bitwise OR in the $ i $ -th scenario.

[Visualizer link](https://codeforces.com/assets/contests/2147/E_HLZmcINLu6bzC9EaTZrI.html) In the first test case: - In the first scenario, we don't have any operations, and therefore the answer is equal to the number of $ 1 $ -bits in the bitwise OR of the original array, $ 0 $ , which has $ 0 $ bits set in its binary representation. - In the second scenario, one way of achieving $ 1 $ bit set in the bitwise OR is increasing $ a_1 $ by $ 1 $ twice, obtaining a bitwise OR of $ 2={(10)}_2 $ . It can be shown that it is the best possible value we can obtain by performing the operation at most twice. - In the third scenario, one way of achieving a result of $ 2 $ is adding $ 1 $ to $ a_1 $ three times, which can be shown to be optimal. Note that you don't have to apply the operation $ 4 $ times. In the second test case: - In the first scenario, we don't have any operations, and therefore the answer is equal to the number of $ 1 $ -bits in the bitwise OR of the original array, which is $ 2 $ . - In the second scenario, one way of achieving a result of $ 3 $ is adding $ 1 $ to $ a_2 $ three times, which can be shown to be optimal.