Given a sequence $a_1, a_2, \dots, a_n$ of length $n$ and a $01$-sequence $b_1, b_2, \dots, b_n$ of length $n$. For $1 \le i < j \le n$, a pair $(i, j)$ is called a match if and only if $b_i = 0$ and $b_j = 1$. A maximal matching scheme $S_{\max}$ is defined as a set of pairs satisfying the following conditions: For any $(u, v) \in S_{\max}$, $1 \le u < v \le n$ and $(u, v)$ is a match; Each integer $1 \le i \le n$ appears at most once in $S_{\max}$; Subject to the above conditions, the number of pairs $(u, v)$ such that $a_u = a_v$ is maximized, i.e., $\sum_{(u, v) \in S_{\max}} [a_u = a_v]$ is maximized; Subject to the above conditions, $|S_{\max}|$ is maximized.

Given $m$ modifications, each modification provides $x, p, q$, representing the update of $(a_x, b_x)$ to $(p, q)$. You need to output the size $|S_{\max}|$ of the maximal matching scheme $S_{\max}$ after each of the $m+1$ states (initially, and after each of the $m$ operations in order).

Input

Read from standard input. The first line contains two integers $n, m$, representing the length of the sequences and the number of operations. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ describing sequence $a$. The third line contains $n$ integers $b_1, b_2, \dots, b_n$ describing sequence $b$. The next $m$ lines each contain three integers $x, p, q$, describing a modification.

Output

Output to standard output. Output $m+1$ lines, each containing one integer, where the $i$-th line represents the value of $|S_{\max}|$ after performing the first $(i-1)$ operations in the input order.

Examples

Input 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

Output 1

0
1
1
2
1
1

Note 1

• Initially, since all $b_i$ are equal to $0$, there are no matches, so the size of the maximal matching scheme is $0$. Output $0$ for the first line.
• After the first modification, $b_2 = 1$, the maximal matching scheme is $\{(1, 2)\}$, so output $1$ for the second line.
• After the first three modifications, sequence $a$ is $1, 2, 1, 2, 2$, and sequence $b$ is $0, 1, 0, 1, 0$. The maximal matching scheme is $\{(1, 2), (3, 4)\}$, so output $2$ for the fourth line. Note that at this time $b_4 = 1, b_5 = 0$, which does not form a match.

Input 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

Output 2

1
1
1
2
3
3
4
4
3
3
2

Subtasks

For all test data: $1 \le n \le 2 \times 10^5$, $0 \le m \le 2 \times 10^5$; For $1 \le i \le n$, $1 \le a_i \le n$, $0 \le b_i \le 1$; * In each modification, $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%): No special restrictions.