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\&verb|&|a_2^\prime\cdots\&verb|&|a_n^\prime=X$ to hold?↵
↵
- How can we ensure $a_1^\prime\&verb|&|a_2^\prime\cdots\&verb|&|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\&verb|&|a_2^\prime\cdots\&verb|&|a_n^\prime=X$ to hold is that each modified value $a_i^\prime$ must satisfy $a_i^\prime\&verb|&|X=X$.↵
↵
So define $up_X(a_i)$ is the minimum non-negative integer such that $(a_i+up_X(a_i))\&verb|&|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\&verb|&|b_2\cdots\&verb|&|b_n$. It satisfies that $Y\&verb|&|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.↵
↵
[Code for reference.](https://mirror.codeforces.com/contest/2161/submission/351171056)↵
↵
### 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).↵
↵
↵
[Code for reference.](https://mirror.codeforces.com/contest/2161/submission/351181254)↵
↵
### 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\&verb|&|(2^i-1)$) and compute it in $O(1)$ time.↵
↵
Note the special case where $X=Y$.↵
↵
[Code for reference.](https://mirror.codeforces.com/contest/2161/submission/351256615)↵
↵
# 中文版本↵
↵
## Hint↵
↵
• 要使 $a_1^\prime\&verb|&|a_2^\prime\cdots\&verb|&|a_n^\prime=X$ 成立的必要条件是什么？↵
↵
• 如何确保 $a_1^\prime\&verb|&|a_2^\prime\cdots\&verb|&|a_n^\prime$ 恰好等于 $X$？↵
↵
• 注意一些边界情况。↵
↵
• 如何加速操作过程？↵
↵
## Solution↵
↵
### Step 1↵
↵
我们首先考虑一个直接的 $O(nq)$ 方法。↵
↵
要使 $a_1^\prime\&verb|&|a_2^\prime\cdots\&verb|&|a_n^\prime=X$ 成立的一个必要条件是每个修改后的值 $a_i^\prime$ 必须满足 $a_i^\prime\&verb|&|X=X$。↵
因此定义 $up_X(a_i)$ 是满足 $(a_i+up_X(a_i))\&verb|&|X=X$ 的最小非负整数。令 $b_i=a_i+up_X(a_i)$。为了计算 $up_X(x)$，我们找到 $x$ 和 $X$ 的二进制表示中不同的最高位 $B$（如果存在）。然后将其设置为 $1$，并将低位调整为符合 $X$。 ↵
↵
调整后，令 $Y=b_1\&verb|&|b_2\cdots\&verb|&|b_n$。它满足 $Y\&verb|&|X=X$。 ↵
↵
接下来，我们需要确保 $Y$ 恰好等于 $X$。类似地，找到不同的最高位 $B$（如果存在）并将其变为 $0$。如果修改 $b_k$ 将 $B$ 位变为 0。可以证明，最优情况下，只需对单个元素进行一次操作即可同时纠正所有较低的不同位。 ↵
↵
当 $n \ge 2$ 时，可能会出现一个问题：如果我们在某个位上修改 $b_k$，而除了 $b_k$ 之外的所有元素在该位上都是 1，那么 $Y \neq X$ 会再次出现。为了避免这种情况，通常最优的操作是选择一个不会引起这种冲突的元素。 ↵
↵
基于此，我们可以轻松编写 $O(nq)$ 的代码并提交。 ↵
↵
[参考代码](https://mirror.codeforces.com/contest/2161/submission/351181254)↵
↵
### Step 2↵
↵
得到 $Y$ 后，我们尝试加速该过程。 ↵
↵
将 $X$ 的位按降序表示为 $x_1,x_2\cdots x_k$。 ↵
↵
我们从高位到低位处理这些位。在第 $i$ 次处理时，所有包含 $x_1,x_2\cdots,x_{i-1}$ 但不包含 $x_i$ 的 $a_i$ 将被处理。这可以通过卷积加容斥解决。↵
↵
[参考代码](https://mirror.codeforces.com/contest/2161/submission/351171056)↵
↵
### Step 3↵
↵
为了使 $Y$ 恰好等于 $X$，我们找到 $X$ 和 $Y$ 不同的最高位 $B$。然后我们寻找一个元素 $a_k$，使得修改它所需的操作次数最少，并且不会向 $Y$ 添加新的位。 ↵
↵
令 $b$ 为第二步中改变的最高位。我们枚举 $[b+1,20]$。如果在第 $i$ 位，0 至少出现两次，则找到低 $i$ 位中值最大的数（即 $a_k\&verb|&|(2^i-1)$）并在 $O(1)$ 时间内计算。 ↵
↵
注意 $X=Y$ 的特殊情况。↵
↵
↵
[参考代码](https://mirror.codeforces.com/contest/2161/submission/351256615)↵
↵
## Reference ↵
↵
[Pinely Round 5 editorial](https://mirror.codeforces.com/blog/entry/147941)
↵
# English Version↵
↵
## Hints↵
↵
- What's the necessary condition for $a_1^\prime\
↵
- How can we ensure $a_1^\prime\
↵
- 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\
↵
So define $up_X(a_i)$ is the minimum non-negative integer such that $(a_i+up_X(a_i))\
↵
After adjustment,let $Y=b_1\
↵
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.↵
↵
[Code for reference.](https://mirror.codeforces.com/contest/2161/submission/351171056)↵
↵
### 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).↵
↵
↵
[Code for reference.](https://mirror.codeforces.com/contest/2161/submission/351181254)↵
↵
### 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\
↵
Note the special case where $X=Y$.↵
↵
[Code for reference.](https://mirror.codeforces.com/contest/2161/submission/351256615)↵
↵
# 中文版本↵
↵
## Hint↵
↵
• 要使 $a_1^\prime\
↵
• 如何确保 $a_1^\prime\
↵
• 注意一些边界情况。↵
↵
• 如何加速操作过程？↵
↵
## Solution↵
↵
### Step 1↵
↵
我们首先考虑一个直接的 $O(nq)$ 方法。↵
↵
要使 $a_1^\prime\
因此定义 $up_X(a_i)$ 是满足 $(a_i+up_X(a_i))\
↵
调整后，令 $Y=b_1\
↵
接下来，我们需要确保 $Y$ 恰好等于 $X$。类似地，找到不同的最高位 $B$（如果存在）并将其变为 $0$。如果修改 $b_k$ 将 $B$ 位变为 0。可以证明，最优情况下，只需对单个元素进行一次操作即可同时纠正所有较低的不同位。 ↵
↵
当 $n \ge 2$ 时，可能会出现一个问题：如果我们在某个位上修改 $b_k$，而除了 $b_k$ 之外的所有元素在该位上都是 1，那么 $Y \neq X$ 会再次出现。为了避免这种情况，通常最优的操作是选择一个不会引起这种冲突的元素。 ↵
↵
基于此，我们可以轻松编写 $O(nq)$ 的代码并提交。 ↵
↵
[参考代码](https://mirror.codeforces.com/contest/2161/submission/351181254)↵
↵
### Step 2↵
↵
得到 $Y$ 后，我们尝试加速该过程。 ↵
↵
将 $X$ 的位按降序表示为 $x_1,x_2\cdots x_k$。 ↵
↵
我们从高位到低位处理这些位。在第 $i$ 次处理时，所有包含 $x_1,x_2\cdots,x_{i-1}$ 但不包含 $x_i$ 的 $a_i$ 将被处理。这可以通过卷积加容斥解决。↵
↵
[参考代码](https://mirror.codeforces.com/contest/2161/submission/351171056)↵
↵
### Step 3↵
↵
为了使 $Y$ 恰好等于 $X$，我们找到 $X$ 和 $Y$ 不同的最高位 $B$。然后我们寻找一个元素 $a_k$，使得修改它所需的操作次数最少，并且不会向 $Y$ 添加新的位。 ↵
↵
令 $b$ 为第二步中改变的最高位。我们枚举 $[b+1,20]$。如果在第 $i$ 位，0 至少出现两次，则找到低 $i$ 位中值最大的数（即 $a_k\
↵
注意 $X=Y$ 的特殊情况。↵
↵
↵
[参考代码](https://mirror.codeforces.com/contest/2161/submission/351256615)↵
↵
## Reference ↵
↵
[Pinely Round 5 editorial](https://mirror.codeforces.com/blog/entry/147941)
