以下では数列 \(A,B\) の最大値を \(M\) とします。制約より \(M< 2^{60} \) です。

---

[1] 操作を逆順に見る

操作を逆から見ることで、この問題の操作の部分を以下のように言い換えられます。

---

• 整数 \( K\ (1\le K \le N)\) を選ぶ。全ての \(i\ (1\leq i \leq K)\) について、\( B_i\) の値を \( B_1\oplus B_2 \oplus \ldots \oplus B_i\) で置き換える。この置き換えは全ての \( i\ (1\leq i \leq K)\) に対して同時に行う。

---

以下、言い換え後の問題について考えます。

---

[2] 操作後の \(B\) の状態の特徴付け

何回か操作を行った後の \(B\) の状態を特徴付けましょう。

\(0\) 回以上操作を行なった後の数列 \(B\) を \(B'\) とすると、各 \(i\) について以下が成り立っていることがわかります。

\[ B'_i = B_i \oplus ((B_1,B_2,\ldots,B_{i-1}) \text{のある部分集合の総XOR})\]

これは、数学的帰納法により証明可能です。

以上より、各 \(i\) について \(A_i\) が \( B_i \oplus ((B_1,B_2,\ldots,B_{i-1}) \text{のある部分集合の総XOR})\) と表せることが構築可能であることの必要条件となっています。

この条件を満たしているかは、掃き出し法により \(O(N\log M)\) で判定できます。

実は、この必要条件を満たす任意の場合について \(70000\) 回以下の操作で \(A\) と \(B\) を一致させられることを以下で説明します。

---

[3] 実際に構築する

以下では[2]で説明した必要条件を満たしていることを前提とします。

操作で \(K\) を選んでも \(B_{K+1}\) 以降には影響しないことから、末尾から \(A\) と \(B\) を揃えていく方針が筋が良さそうです。\(\lceil \log_2M\rceil\) 回の操作で末尾を揃えられれば、これを \(N\) 回繰り返すことで \(N\lceil \log_2M\rceil\) 回の操作で \(A\) と \(B\) を一致させられ、操作回数を \(70000\) 回以下に抑えられます。

以下、\(A_i\) と \(B_i\) を \(\lceil \log_2M\rceil\) 回の操作で一致させる方法を考えます。

末尾から揃えていることから、 \(i\) より大きい \(K\) を選ぶことはできません。 \(A_i=B_i\) の場合は自明なので無視すると、\(A_i=B_i\) にするためには最後に \(K=i\) とする操作を行う必要があります。

\(K=i\) の操作を行うと \(B_i = B_1\oplus B_2 \oplus \ldots \oplus B_{i-1} \oplus B_i\) となるので、結局 \(B_1\oplus B_2 \oplus \ldots \oplus B_{i-1} \oplus B_i\) を \(A_i\) に一致させる（\(B_1\oplus B_2 \oplus \ldots \oplus B_{i-1} \oplus B_i\oplus A_i=0\) とする）とよいです。

ここで、数列の基底に着目します。\(i=1,2,\ldots\) の順に掃き出し法を行い基底を定めるとき、いかなる操作の後もその要素が基底であるかどうかは変化しないことがわかります。この性質は、[2]での \(B\) の特徴から従います。

また、\(j\) の位置に基底があるとき、 \(K=j+1\) として操作を行うと、\(j\) の右側の基底に関しては変化させずに、\(B_j\) の分 \(B_1\oplus B_2 \oplus \ldots \oplus B_{i-1} \oplus B_i\) を変化させられることがわかります。

このことから、降順に基底のみを見ていき、\(B_1\oplus B_2 \oplus \ldots \oplus B_{i-1} \oplus B_i\oplus A_i=0\) とするためにはその基底に操作が必要かを確かめ、必要な場合実際に操作を行うことにより、\(\lceil \log_2M\rceil\) 回の操作で \(A_i=B_i\) と出来ることがわかりました。

以上より[2]の必要条件を満たす場合常に \(N\lceil \log_2M\rceil\) 回程度の操作で \(A\) と \(B\) を一致させられ、これは制約より十分 \(70000\) より小さいです。