Xiao Ming has a tree with $n$ nodes rooted at $1$. Each non-root node has a light, and he has a permutation $a_1, a_2, \dots, a_{n-1}$ of $2 \sim n$. He also has a counter, initially set to $0$.

He turns on the $n-1$ lights in the order given by the permutation. After each light is turned on, he checks if the entire tree is "beautiful." If it is beautiful, the counter increases by the number of connected components formed by the currently lit nodes.

The value of the counter after $n-1$ operations is the answer for this tree.

A tree is beautiful if and only if for every lit node, all nodes in its subtree are also lit.

Xiao Ming thinks this problem is too simple, so he decides to make the tree dynamic. After the initial query, he will remove one edge from the tree and add another, ensuring the result remains a tree. He wants to know the answer for the tree after each modification, resetting the counter to $0$ and re-performing the lighting process.

Input

The input is read from standard input.

The first line contains two integers $n$ and $m$, representing the number of nodes in the tree and the number of modifications, respectively.

The next $n-1$ lines each contain two integers, representing an edge.

The next line contains $n-1$ integers $a_i$, representing a permutation of $2 \sim n$.

The next $m$ lines each contain four integers $x_1, y_1, x_2, y_2$, representing the removal of the edge between $x_1$ and $y_1$ and the addition of an edge between $x_2$ and $y_2$. It is guaranteed that the modifications are valid.

Output

The output is written to standard output.

There are $m+1$ lines in total. The first line represents the answer for the initial tree.

The next $m$ lines represent the answer for the tree after each modification.

Examples

Input 1

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

Output 1

13
15
4
6
2
2
10
7
8
8
7

Input 2

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

Output 2

3
2
2
1
2
4
4
3
3
3
3

Constraints

• Subtask 1 (10 points): Guaranteed $2 \leq n \leq 500000$, $m = 0$.
• Subtask 2 (20 points): Guaranteed $2 \leq n \leq 8000$, $0 \leq m \leq 8000$.
• Subtask 3 (70 points): Guaranteed $2 \leq n \leq 500000$, $0 \leq m \leq 500000$.