**The only differences between this chapter and [chapter 1](https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-2/problems/D1) is that here, \(A_i \in \{1, 2\}\), and you may only swap adjacent elements of \(A_i\) with a single operation.**

As a Metal Platforms employee, you place a high value on your work-life balance. Boss Rob has assigned you \(N\) tasks, the \(i\)th of which takes \(A_i\) minutes to finish, where \(A_i\) is either **\(\mathbf{1}\) or \(\mathbf{2}\)**.

You may reorder your tasks, where each *operation* lets you **swap any two adjacent elements** of \(A\) (\(A_i\) and \(A_j\) for some \(i\) and \(j\) such that \(|i - j| = 1\)).

To reflect how often task requirements change in the real world, there will be \(M\) updates made to the task completion times, with the \(i\)th update setting \(A_{X_i}\) to \(Y_i\).

After completing the \(i\)th update, you would like to know if it's possible to balance the time spent at work versus at home, namely if you hope to finish the first \(Z_i\) tasks at work and the rest at home. Specifically, let \(Q_i\) be the minimum number of swap operations which must be theoretically performed so that \(A_1 + ... + A_{Z_i} = A_{Z_i + 1} + ... + A_{N}\), with \(Q_i = -1\) if it's impossible. Note that it's possible for \(Q_i\) to be \(0\), if the subarrays already have equal sums.

To reduce the size of the output, please compute the sum of \(Q_1\), ..., \(Q_M\).

# Constraints

\(1 \le T \le 95\)
\(2 \le N \le 1{,}000{,}000\)
\(1 \le M \le 1{,}000{,}000\)
\(A_i, Y_i \in \{1, 2\}\)
\(1 \le X_i \le N\)
\(1 \le Z_i \le N-1\)

The sum of \(N+M\) across all test cases is at most \(7{,}000{,}000\).

# Input Format

Input begins with a single integer \(T\), the number of test cases. For each test case, there is first a line containing two space-separated integers \(N\) and \(M\). Then, there is a line containing \(N\) digits, \(A_1\), \(A_2\), ..., \(A_N\). Then, \(M\) lines follow, the \(i\)th of which contains three space-separated integers \(X_i\), \(Y_i\), and \(Z_i\).

# Output Format

For the \(i\)th test case, output `"Case #i: "` followed by a single integer, \(Q_1 + ... + Q_M\).

# Sample Explanation

The first case is depicted below:

{{PHOTO_ID:2337609416394611|WIDTH:700}}

We start with \(A = [1, 2]\). The first update yields \(A=[1, 1]\) with \(Z_1 = 1\). The first and second tasks are already equal, so \(Q_1 = 0\) as no swaps are necessary. The second update yields \(A=[2, 1]\), and after the third update we still have \([2, 1]\). In neither case can we equally split the tasks, so \(Q_2 = Q_3 = -1\). The final answer is \(0 + (-1) + (-1) = -2\).

The second case is depicted below:

{{PHOTO_ID:402660235386017|WIDTH:700}}

We start with \(A = [1, 1, 1, 2]\). The first update yields \(A=[2, 1, 1, 2]\) with \(Z_1 = 2\). The two subarrays both sum to \(3\) already, so \(Q_1 = 0\). The second update yields \(A=[2, 2, 1, 2]\). It's impossible to split the tasks equally, so \(Q_2 = -1\). The third update yields \(A=[2, 2, 1, 1]\) with \(Z_3 = 2\). We can swap the second and third tasks so that both halves of the array sum to \(3\), so \(Q_3 = 1\). The final answer is \(0 + (-1) + 1 = 0\).

In the third case, we start with \(A = [1, 1, 1, 1, 2, 2, 2, 2]\). With the updates, we get:
- \(A = [1, 1, 1, 1, 2, 2, 2, 2], Z_1 = 4\) and \(Q_1 = 4\): move the left two \(2\)s two spaces left
- \(A = [1, 1, 1, 1, 2, 2, 2, 2], Z_2 = 3\) and \(Q_2 = 12\): move the left three \(2\)s four spaces left
- \(A = [1, 1, 1, 1, 2, 2, 2, 2], Z_3 = 5\) and \(Q_3 = 0\)
- \(A = [2, 1, 1, 1, 2, 2, 2, 2], Z_4 = 4\) and \(Q_4 = -1\)
- \(A = [2, 1, 2, 1, 2, 2, 2, 2], Z_5 = 4\) and \(Q_5 = 1\): swap \(A_4\) and \(A_5\)

The final answer is \(4 + 12 + 0 + (-1) + 1 = 16\).