CF2161G Bitwise And Equals

There is an array of integers $ a_1, a_2, \ldots, a_n $ , and there is an integer $ X $ . You may perform the following operation zero or more times: - Select $ i $ , and increase $ a_i $ by one. Let $ a' $ be the final state of the array. Your goal is to perform the operation above the smallest number of times such that $ a'_1 \,\&\, a'_2 \,\&\, \ldots \,\&\, a'_n = X $ . $ \& $ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND). There are $ q $ such query integers $ X $ : $ X_1, X_2, \ldots, X_q $ . Compute the answer for each $ X = X_i $ . Note that all queries are processed separately and independently, from the same initial state $ a $ .

The first line contains integers $ n $ and $ q $ ( $ 2 \le n \le 200\,000 $ , $ 1 \le q \le 200\,000 $ ) — the length of the array and the number of queries. The second line contains integers $ a_1, a_2, \ldots, a_n $ (for each $ i $ , $ 0 \le a_i < 2^{20} $ ). The next $ q $ lines each contain a single integer $ X_i $ ( $ 0 \le X_i < 2^{20} $ ).

For each query $ i $ out of $ q $ , print the smallest number of operations to get to the array $ a' $ such that $ a'_1 \,\&\, a'_2 \,\&\, \ldots \,\&\, a'_n = X_i $ . It's possible to show, that it's always possible to obtain such array $ a' $ in finite number of operations.

For the first query, you can increase $ i = 3 $ ( $ a_i = 7 $ ) and get the array $ a = [6, 4, 8, 5, 4] $ , then $ 6 \,\&\, 4 \,\&\, 8 \,\&\, 5 \,\&\, 4 = 0 $ . For the third query, original array already matches condition: $ 6 \,\&\, 4 \,\&\, 7 \,\&\, 5 \,\&\, 4 = 4 $ .