Maximal Matching with Same‐Value Priority

Given an integer sequence \(a_1,a_2,\ldots,a_n\) and a binary sequence \(b_1,b_2,\ldots,b_n\), a pair \((i,j)\) with \(1\le i<j\le n\) is called a match if and only if \(b_i=0\) and \(b_j=1\).

We define a maximal matching scheme \(S_{\max}\) as a set of matching pairs satisfying:

1. For every \((u,v)\in S_{\max}\), we have \(1\le u<v\le n\) and \((u,v)\) is a match.
2. Each index \(1\le i\le n\) appears in at most one pair in \(S_{\max}\).
3. Among all such matchings, the number of pairs with \(a_u=a_v\) is maximized, i.e. maximize \(\displaystyle \sum_{(u,v)\in S_{\max}}[a_u=a_v]\).
4. Subject to the above, the total number of pairs \(|S_{\max}|\) is maximized.

You are also given \(m\) update operations. Each operation is given by three integers \(x, p, q\), which means updating the pair \((a_x, b_x)\) to \((p,q)\). Initially, before any updates, you should compute \(|S_{\max}|\) for the original sequence. Then, after each update (applied in the given order), recompute \(|S_{\max}|\) for the new sequence.

Note: All formulas are written in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(m\): the length of the sequences and the number of updates.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\).

The third line contains a binary string of length \(n\) (each character is either '0' or '1'), representing \(b_1, b_2, \ldots, b_n\).

Each of the next \(m\) lines contains three integers \(x, p, q\) (with \(1\le x\le n\) and \(q\in\{0,1\}\)), indicating that \((a_x, b_x)\) is updated to \((p,q)\).

outputFormat

Output \(m+1\) lines. The \(i\)-th line (\(1\le i\le m+1\)) should contain a single integer representing the size of the maximal matching scheme \(|S_{\max}|\) after applying the first \(i-1\) updates.

sample

5 2
1 2 1 2 1
01011
3 2 1
5 2 0

2
1
1