A binary tree is a hierarchical structure consisting of $n$ nodes labeled with numbers from $1$ to $n$. Each node $k$ in the tree can have a left child $l_k$ and a right child $r_k$. If node $m$ is a child of node $k$, we say that $k$ is the parent of node $m$. The node labeled $1$ is called the root of the binary tree, and it is always true that the root has no parent, while every other node has a unique parent. The descendants of a node $k$ are all nodes that can be reached from $k$ by following a sequence of parents, and it holds that all nodes (except the root itself) are descendants of the tree root. A subtree is a binary tree consisting of a node $k$ and all its descendants. Each node contains a value — an integer between $0$ and $10^9$ inclusive.

A binary tree is called a binary search tree if for every node $k$ in the tree, the following holds: If $k$ has a left child $l_k$, then the value of node $l_k$ and all its descendants is less than or equal to the value of node $k$. If $k$ has a right child $r_k$, then the value of node $r_k$ and all its descendants is greater than or equal to the value of node $k$.

Note that every subtree of a binary search tree must also be a binary search tree.

You are given a binary tree and $m$ commands that must be processed in the order they are given. Each command is of the form "$k_i$ $x_i$", which means that the value of node $k_i$ must be set to $x_i$. For each command, you must consider the tree immediately after it has been executed and determine the number of subtrees that are binary search trees.

Input

The first line of input contains the natural numbers $n$ and $m$ — the number of nodes in the tree and the number of commands. This is followed by $n$ lines, where the $k$-th of these $n$ lines contains two integers $l_k$ and $r_k$ ($0 \le l_k, r_k \le n$) — the labels of the left and right children of node $k$. If a node does not have a left or right child, $l_k$ or $r_k$ will be zero.

The next line contains $n$ integers $v_1, v_2, \dots, v_n$ ($0 \le v_k \le 10^9$) — the initial values stored in the nodes from node $1$ to node $n$.

Following this are $m$ lines, where the $i$-th of these $m$ lines contains two integers $k_i$ and $x_i$ ($1 \le k_i \le n, 0 \le x_i \le 10^9$) — the label of the node and the new value to be stored in the node.

Output

Print $m$ lines. In the $i$-th line, print the number of subtrees that are binary search trees at the moment immediately after processing the $i$-th command from the input.

Subtasks

Examples

Input 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

Output 1

4
5
5
6
4

Input 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

Output 2

3
3
3
6
6
6
6
8
7
8

Note

Explanation of the first example: The appearance of the tree at the beginning and after processing the first three commands is given below. The underlined value is the one that changed in the command, while the roots of all subtrees that are binary search trees are highlighted in color.