给定长度为 $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}|$ 的值。

样例 #1

样例输入 #1

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

样例输出 #1

0
1
1
2
1
1

样例 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$，并不构成匹配。

样例 #2

样例输入 #2

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

样例输出 #2

1
1
1
2
3
3
4
4
3
3
2

子任务

对于所有测试数据，

• $1\le n\le 2\times {10}^5$，$0\le m\le 2\times {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\mathrm{\%}$）：$n\le 100$，$m=0$。
• Subtask 2（$15\mathrm{\%}$）：$n\le 2\times {10}^3$，$m=0$。
• Subtask 3（$20\mathrm{\%}$）：$m=0$。
• Subtask 4（$15\mathrm{\%}$）：$a_i,p\le 2$。
• Subtask 5（$20\mathrm{\%}$）：$n,m\le {10}^5$。
• Subtask 6（$20\mathrm{\%}$）：无特殊限制。