Two language versions are available in order to serve both codeforces and luogu community.
English Version
Hints
What's the necessary condition for $$$a_1^\prime&a_2^\prime\cdots&a_n^\prime=X$$$ to hold?
How can we ensure $$$a_1^\prime&a_2^\prime\cdots&a_n^\prime$$$ is exactly equal to $$$X$$$?
Pay attention to some corner cases.
How can we optimize the procedure?
Solution
Step 1
We begin by considering a straightforward $$$O(nq)$$$ approach.
A necessary condition for $$$a_1^\prime&a_2^\prime\cdots&a_n^\prime=X$$$ to hold is that each modified value $$$a_i^\prime$$$ must satisfy $$$a_i^\prime&X=X$$$.
So define $$$up_X(a_i)$$$ is the minimum non-negative integer such that $$$(a_i+up_X(a_i))&X=X$$$. Let $$$b_i=a_i+up_X(a_i)$$$. To compute $$$up_X(x)$$$,we locate the highest bit $$$B$$$ (if any) where the binary representations of $$$x$$$ and $$$X$$$ differ.Then set it to $$$1$$$ and keep the lower bits conform to $$$X$$$.
After adjustment,let $$$Y=b_1&b_2\cdots&b_n$$$. It satisfies that $$$Y&X=X$$$.
Next, we need to ensure that $$$Y$$$ is exactly equal to $$$X$$$. Similarly, locate the highest bit $$$B$$$ (if any) and turn it to $$$0$$$. If $$$b_k$$$ is modified to turn $$$B$$$ bit to $$$0$$$. It can be shown that optimally, only one operation on a single element is sufficient to correct all lower differing bits as well.
When $$$n\ge 2$$$, a potential issue arises: if we modify $$$b_k$$$ on a bit where every element except $$$b_k$$$ is $$$1$$$ , $$$Y\neq X$$$ again. To avoid this, it is generally optimal to operate on an element other than the one that would cause such a conflict.
Based on this, we can easily write a $$$O(nq)$$$ code and submit.
Step 2
After we get $$$Y$$$, we try to speed up the procedure.
Let the bits of $$$X$$$ be denoted as $$$x_1,x_2\cdots x_k$$$ in descending order.
We process the bits from the highest to the lowest. At the $$$i$$$-th time,all $$$a_i$$$ which contains $$$x_1,x_2\cdots,x_{i-1}$$$ but not $$$x_i$$$ are processed. It can be calculated by AND Fast Walsh-Hadamard Transform (FWT) and the Principle of Inclusion-Exclusion (PIE).
Step 3
To make $$$Y$$$ exactly $$$X$$$, we identify the highest bit $$$B$$$ where $$$X$$$ and $$$Y$$$ differ. We then look for an element $$$a_k$$$ such that modifying it minimizes the number of operations required and it won't add new bits to $$$Y$$$.
Let $$$b$$$ be the highest bit changed in Step 2. We enumerate $$$[b+1,20]$$$. If at digit $$$i$$$, $$$0$$$ exists at least twice,find the number with with the largest value in the lower $$$i$$$ bits (i.e. $$$a_k&(2^i-1)$$$) and compute it in $$$O(1)$$$ time.
Note the special case where $$$X=Y$$$.
中文版本
Hint
• 要使 $$$a_1^\prime&a_2^\prime\cdots&a_n^\prime=X$$$ 成立的必要条件是什么？
• 如何确保 $$$a_1^\prime&a_2^\prime\cdots&a_n^\prime$$$ 恰好等于 $X$？
• 注意一些边界情况。
• 如何加速操作过程？
Solution
Step 1
我们首先考虑一个直接的 $$$O(nq)$$$ 方法。
要使 $$$a_1^\prime&a_2^\prime\cdots&a_n^\prime=X$$$ 成立的一个必要条件是每个修改后的值 $$$a_i^\prime$$$ 必须满足 $a_i^\prime&X=X$。 因此定义 $$$up_X(a_i)$$$ 是满足 $$$(a_i+up_X(a_i))&X=X$$$ 的最小非负整数。令 $$$b_i=a_i+up_X(a_i)$$$。为了计算 $$$up_X(x)$$$，我们找到 $$$x$$$ 和 $$$X$$$ 的二进制表示中不同的最高位 $B$（如果存在）。然后将其设置为 $1$，并将低位调整为符合 $X$。
调整后，令 $Y=b_1&b_2\cdots&b_n$。它满足 $Y&X=X$。
接下来，我们需要确保 $$$Y$$$ 恰好等于 $$$X$$$。类似地，找到不同的最高位 $$$B$$$（如果存在）并将其变为 $$$0$$$。如果修改 $$$b_k$$$ 将 $$$B$$$ 位变为 0。可以证明，最优情况下，只需对单个元素进行一次操作即可同时纠正所有较低的不同位。
当 $$$n \ge 2$$$ 时，可能会出现一个问题：如果我们在某个位上修改 $$$b_k$$$，而除了 $$$b_k$$$ 之外的所有元素在该位上都是 1，那么 $$$Y \neq X$$$ 会再次出现。为了避免这种情况，通常最优的操作是选择一个不会引起这种冲突的元素。
基于此，我们可以轻松编写 $$$O(nq)$$$ 的代码并提交。
Step 2
得到 $$$Y$$$ 后，我们尝试加速该过程。
将 $$$X$$$ 的位按降序表示为 $x_1,x_2\cdots x_k$。
我们从高位到低位处理这些位。在第 $$$i$$$ 次处理时，所有包含 $$$x_1,x_2\cdots,x_{i-1}$$$ 但不包含 $$$x_i$$$ 的 $$$a_i$$$ 将被处理。这可以通过卷积加容斥解决。
Step 3
为了使 $$$Y$$$ 恰好等于 $$$X$$$，我们找到 $$$X$$$ 和 $$$Y$$$ 不同的最高位 $$$B$$$。然后我们寻找一个元素 $$$a_k$$$，使得修改它所需的操作次数最少，并且不会向 $$$Y$$$ 添加新的位。
令 $$$b$$$ 为第二步中改变的最高位。我们枚举 $$$[b+1,20]$$$。如果在第 $$$i$$$ 位，0 至少出现两次，则找到低 $$$i$$$ 位中值最大的数（即 $$$a_k&(2^i-1)$$$）并在 $$$O(1)$$$ 时间内计算。
注意 $$$X=Y$$$ 的特殊情况。
