**The only differences between this chapter and [chapter 2](https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-2/problems/D2) is that here, \(A_i \in \{1, 2, 3\}\), and you may swap any two 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, 2}\), or \(\mathbf{3}\)**.

You may reorder your tasks, where each *operation* lets you **swap any two elements** of \(A\).

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 100\)
\(2 \le N \le 1{,}000{,}000\)
\(1 \le M \le 1{,}000{,}000\)
\(A_i, Y_i \in \{1, 2, 3\}\)
\(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:463552492491498|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=[1, 3]\) with \(Z_2 = 1\). Whether or not we swap these tasks, they can never be equal, so \(Q_2 = -1\). The final answer is \(0 + (-1) = -1\).

The second case is depicted below:

{{PHOTO_ID:774910673835114|WIDTH:700}}

We start with \(A = [1, 1, 3, 3]\). The first update yields \(A=[1, 1, 3, 1]\). We need the sum of the first three tasks to equal the fourth. We can swap the third and fourth tasks to get \(1 + 1 + 1 = 3\), so \(Q_1 = 1\). The second update yields \(A=[3, 1, 3, 1]\). We need the sum of the first two tasks to equal the sum of the last two. This is already true, so \(Q_2 = 0\). The final answer is \(1 + 0 = 1\).

In the third case, we start with \(A = [1, 2, 3, 3, 3, 3]\). With the updates, we get:
- \(A = [1, 2, 3, 3, 3, 2], Z_1 = 3, Q_1 = 1\): we can swap \(A_1\) and \(A_6\)
- \(A = [1, 2, 3, 1, 3, 2], Z_2 = 2, Q_2 = 2\): we can swap both \(3\)s to the front
- \(A = [1, 2, 1, 1, 3, 2], Z_3 = 2, Q_3 = 1\): we can swap \(A_1\) and \(A_5\)
- \(A = [3, 2, 1, 1, 3, 2], Z_4 = 5, Q_4 = -1\): impossible

The final answer is \(1 + 2 + 1 + (-1) = 3\).