题目描述

给定长度为 $n$ 的整数序列 $a_1,a_2,\cdots,a_n$ 和长度为 $n$ 的 $01$ 序列 $b_1, b_2, \cdots , b_n$。

对于 $1 \le i < j \le n$，称二元组 $(i, j)$ 构成匹配当且仅当 $b_i = 0$ 且 $b_j = 1$。

定义极大匹配方案 $S_{\max}$ 为满足以下所有条件的二元组集合：

• 对于任意 $(u, v) \in S_{\max}$，$1 \le u < v \le n$ 且 $(u, v)$ 构成匹配；
• 每一个整数 $1 \le i \le n$ 在 $S_{\max}$ 中出现至多一次；
• 在满足以上条件的前提下，满足 $a_u = a_v$ 的二元组 $(u, v)$ 数量最多，即 $\displaystyle \sum_{(u,v)\in S_{\max}}[a_u=a_v]$ 最大；
• 在满足以上条件的前提下，$|S_{\max}|$ 最大。

给定 $m$ 次修改，每次修改给出 $x, p, q$，表示将 $(a_x, b_x)$ 修改为 $(p, q)$。

你需要对于每个 $1 \le i \le m + 1$ 求出：按输入顺序依次进行前 $(i - 1)$ 次操作后，极大匹配方案 $S_{\max}$ 的大小 $|S_{\max}|$。

输入格式

从标准输入读入数据。

输入的第一行两个整数 $n, m$，表示序列长度和操作次数。

第二行 $n$ 个整数 $a_1, a_2, \cdots , a_n$ 描述序列 $a$。

第三行 $n$ 个整数 $b_1, b_2, \cdots , b_n$ 描述序列 $b$。

接下来 $m$ 行每行三个整数 $x, p, q$，描述一次修改。

输出格式

输出到标准输出。

输出 $(m + 1)$ 行，每行一个整数，第 $i$ 行表示按输入顺序依次进行前 $(i - 1)$ 次操作后 $|S_{\max}|$ 的值。

5 5
1 2 1 1 2
0 0 0 0 0
2 2 1
4 2 0
4 2 1
2 2 0
1 1 1

0
1
1
2
1
1

10 10
2 1 2 2 2 2 1 2 2 2
1 1 0 0 0 0 1 0 0 0
3 2 0
5 1 0
9 1 1
4 2 1
8 1 1
2 1 0
1 2 1
8 2 0
1 1 1
9 1 0

1
1
1
2
3
3
4
4
3
3
2

提示

【样例 $1$ 解释】

• 初始情况，由于所有的 $b_i$ 都等于 $0$，因此没有二元组构成匹配，极大匹配方案的大小为 $0$，故第一行输出 $0$。
• 进行第一次修改后，$b_2 = 1$，极大匹配方案为 $\{(1, 2)\}$，故第二行输出 $1$。
• 进行前三次修改后，序列 $a$ 为 $[1,2,1,2,2]$，序列 $b$ 为 $[0,1,0,1,0]$。极大匹配方案为 $\{(1, 2), (3, 4)\}$，故第四行输出 $2$。注意此时 $(4, 5)$ 有 $b_4 = 1$，$b_5 = 0$，并不构成匹配。

子任务

对于所有测试数据，

• $1 \le n \le 2 × 10^5$，$0 \le m \le 2 × 10^5$；
• 对于 $1 \le i \le n$，$1 \le a_i \le n$，$0 \le b_i \le 1$；
• 每次修改中有 $1 \le x \le n$，$1 \le p \le n$，$0 \le q \le 1$。

• Subtask 1（$10\%$）：$n \le 100$，$m = 0$。
• Subtask 2（$15\%$）：$n \le 2 \times 10^3$，$m = 0$。
• Subtask 3（$20\%$）：$m = 0$。
• Subtask 4（$15\%$）：$a_i, p \le 2$。
• Subtask 5（$20\%$）：$n, m \le 10^5$。
• Subtask 6（$20\%$）：无特殊限制。