In this editorial, let \(A\) and \(B\) denote the sequence before and after the operations, respectively.

[1] Characterization of the sequence after the operations

For \(B\), the sequence after the operations, the following holds:

• \(A_i\oplus A_j = B_i\oplus B_j\) for every \(i, j\).
• If at least one operation is done, \(B_i = 0\) for some \(i\).

The former property can be seen from the fact that \(a\oplus b = (a\oplus x) \oplus (b\oplus x)\) for any non-negative integers \(a, b, x\). The former property can be seen from the fact that, if at least one operation is done, the term that was equal to the last chosen \(x\) becomes \(0\).

From these properties, the sequence after the operations, \(B\), must be one of the following.

• The same sequence as the sequence \(A\) before the operation (when doing zero operations).
• A sequence determined by \(B_i = A_i\oplus A_k\) (\(1\leq i\leq N\)) for some \(k\).

On the other hand, these sequences can be obtained as the sequence \(B\) after the operations (by doing zero or one operation).

[2] Computing the answer

Now we have determined all possible variants of the sequence \(B\) after the operations. If we can compute \(\sum_{i=1}^N B_i\) for all of them, we can find the answer.

Thus, for each \(x\in \{0, A_1, \ldots, A_N\}\), we want to compute \(\sum_{i=1}^N (A_i\oplus x)\). Let us choose \(K\) so that \(\max_i A_i < 2^K\) and do the computations as follows.

• For each \(k (0\leq k < K)\), compute the sum of the digits of \((A_i\oplus x)\) in \(2^k\)’s place.
• Sum up the results.

This can be done as follows, in the following complexity.

• For each \(k\), precompute the numbers of \(0\)s and \(1\)s among the digits of \(A_i\) in \(2^k\)’s place (in \(\Theta(NK)\) time).
• Use these counts to compute \(\sum_{i} (A_i\oplus x)\) for each \(x\) (in \(\Theta(K)\) time for each \(x\), for a total of \(\Theta(NK)\) time).

Summing up the above, the problem can be solved in \(\Theta(NK)\) time.

• Sample Code (Python)：https://atcoder.jp/contests/arc135/submissions/29030561