This problem is a harder version of Problem C of The 3rd Universal Cup Semifinals (which I authored).

Let us restate the necessary and sufficient condition for a sequence \(B=(B_1, \dots, B_k)\) of length \(k\) to be good in terms of the amounts used in the operations. Let \(x_i\) be the sum of the integers chosen for operations on \(B_i\) and \(B_{i+1}\). For convenience, set \(x_0 = x_k = 0\). Then all elements can be made equal to an integer \(C\) if and only if there exist integers \(x_1, x_2, \dots, x_{k-1}\) satisfying

\[B_i + 2 x_{i-1} + x_i = C\]

Let us transform this condition. Set \(T_i = C - 3 x_i\), and for each integer \(a\), consider the map

\[f_a (t) = \frac{3a-t}{2}\]

This map has a special restriction: the domain of \(t\) is limited to values for which the right-hand side is an integer. In other words, we must not evaluate \(f_a(t)\) at a value \(t\) for which the result is not an integer.

Using \(T_i, f_a\) to rewrite the necessary and sufficient condition above gives

\[T_0 = T_k = C, T_{i-1} = f_{B_i}(T_i)\]

Therefore, defining

\[F_B = f_{B_1} \circ f_{B_2} \circ \dots \circ f_{B_k}\]

we see that if \(B\) is good, there exists an integer \(C\) satisfying \(F_B(C) = C\).

Conversely, suppose there exists an integer \(C\) such that \(F_B(C) = C\). Taking the recurrence \(\text{mod }3\) gives \(T_{i-1} \equiv T_i \pmod{3}\), so

\[x_i = \frac{C - T_i}{3}\]

is an integer and satisfies the original equation.

Thus, we have shown that \(B\) is good if and only if there exists an integer \(C\) satisfying \(F_B(C) = C\).

Let us examine the function \(F_B\) more closely. The following statements hold.

Lemma 1

For an interval of length \(m\), the corresponding \(F\) can be represented using integers \(0 \leq r \lt 2^m, d, \varepsilon=(-1)^m\) as follows:

\[\operatorname{dom} F = \lbrace r+2^m z \vert z \in \mathbb{Z} \rbrace \]

\[F(r + 2^m z) = d + \varepsilon z\]

The proof follows by induction.

Lemma 2

The fixed point of \(F\) lies in \(I = [-10^9, 2 \times 10^9]\).

(Proof) For \(0 \leq a \leq 10^9\) and \(t \in I\), we have \(-10^9 \leq f_a(t) \leq 2 \times 10^9\). Thus, if the domain of \(f_a\) were the real numbers, \(f_a\) would map \(I\) into \(I\).

Also, by Lemma \(1\), if the maps \(f\) had real domains, \(F\) would be an affine function with slope \((-1/2)^m\). This slope is never \(1\), so the real fixed point is unique.

Therefore, the real fixed point exists within \(I\), and when restricting the domain to integers, it is enough to examine \(I\). (End of proof)

Based on these observations, consider storing \(F_X\) at the segment tree interval corresponding to a sequence \(X\). A direct representation would involve numbers whose digit counts grow proportionally to \(|X|\), so use the fact that only inputs within \(I\) need to be considered. The width of \(I\) is \(3 \times 10^9 \lt 2^{32}\), so if \(m \geq 32\), at most \(1\) integer in \(I\) can have the form \(r + 2^m z\). Represent each segment tree interval as follows:

• If its length is at most \(31\), store \((m, r, d, \varepsilon)\).
• If its length is at least \(32\), use one of the following two representations:
  • If the domain within \(I\) consists of \(1\) point, store its input and output.
  • If the domain within \(I\) is empty, record that it is empty.

This lets us perform every function composition in \(\mathrm{O}(1)\) time.

To answer a query, determine whether there exists \(C\) satisfying \(F(C) = C\). This is easy when the domain is empty or consists of \(1\) point. For a map stored as \((m,r,d,\varepsilon)\), solve

\[r + 2^m z = d + \varepsilon z\]

and check the resulting \(C\).

Implementing these ideas appropriately solves the problem in \(\mathrm{O}(N+ Q \log N)\) time, which is sufficiently fast.