二叉树是一种层次结构，由编号为 $1$ 到 $n$ 的 $n$ 个节点组成。树中的每个节点 $k$ 可以有一个左儿子 $l_k$ 和一个右儿子 $r_k$。如果节点 $m$ 是节点 $k$ 的儿子，则称 $k$ 是 $m$ 的父亲。编号为 $1$ 的节点称为二叉树的根，根节点没有父亲，而其他每个节点都有唯一的父亲。节点 $k$ 的子孙是指所有通过沿着父亲指针向上能够到达 $k$ 的节点。显然，除了根节点自身以外，所有节点都是根节点的子孙。子树是由某个节点 $k$ 及其所有子孙组成的二叉树。每个节点上都写有一个值——一个介于 $0$ 到 $10^9$ 之间的整数（含端点）。

如果对于树中的每个节点 $k$，都满足以下条件，则称该二叉树为二叉搜索树：

• 如果 $k$ 有左儿子 $l_k$，则 $l_k$ 及其所有子孙的值都小于或等于节点 $k$ 的值。
• 如果 $k$ 有右儿子 $r_k$，则 $r_k$ 及其所有子孙的值都大于或等于节点 $k$ 的值。

请注意，二叉搜索树的任何子树也必须是二叉搜索树。

给定一棵二叉树以及 $m$ 个操作，需要按照给定的顺序依次处理。每个操作的格式为 "$k_i\ x_i$"，表示需要将节点 $k_i$ 的值修改为 $x_i$。对于每个操作，需要求出在执行该操作后，树中共有多少个子树是二叉搜索树。

输入格式

第一行包含两个正整数 $n$ 和 $m$ — 树的节点数和操作数。

接下来的 $n$ 行中，第 $k$ 行包含两个整数 $l_k$ 和 $r_k$ ($0 \le l_k, r_k \le n$) — 分别表示节点 $k$ 的左儿子和右儿子的编号。如果节点没有左儿子或右儿子，则对应的 $l_k$ 或 $r_k$ 为 $0$。

下一行包含 $n$ 个整数 $v_1, v_2, \dots, v_n$ ($0 \le v_k \le 10^9$) — 节点 $1$ 到 $n$ 的初始值。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $k_i$ 和 $x_i$ ($1 \le k_i \le n$, $0 \le x_i \le 10^9$) — 表示要修改的节点编号以及写入该节点的新值。

输出格式

输出 $m$ 行。在第 $i$ 行中，输出在处理完输入的第 $i$ 个操作后，当前树中是二叉搜索树的子树数量。

子任务

样例

输入样例 1

6 5
2 3
4 0
5 6
0 0
0 0
0 0
4 1 3 2 2 5
3 3
2 2
3 5
5 4
6 1

输出样例 1

4
5
5
6
4

输入样例 2

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

输出样例 2

3
3
3
6
6
6
6
8
7
8

说明

第一个样例的解释：

初始状态以及处理前三个操作后的树的形态如下图所示。下划线标出了在操作中被修改的值，而被着色的节点是所有作为二叉搜索树的子树的根节点。