Background

JYY has recently learned an advanced technique for processing tree structures called "Heavy-Light Decomposition." This technique partitions the edges of a tree into light edges and heavy edges. Connected heavy edges form several disjoint paths on the tree. "Heavy-Light Decomposition" ensures that any path from a node in the tree to the root passes through at most $O(\log N)$ different heavy paths.

Description

If you are not familiar with Heavy-Light Decomposition, JYY provides a brief introduction here: For any node $u$ in a rooted tree, we use $\text{size}(u)$ to denote the number of nodes in the subtree rooted at $u$. Among all children of $u$, we select the child $v$ with the largest $\text{size}(\cdot)$ value and set the edge $\langle u, v \rangle$ as a heavy edge. The edges between $u$ and its other children are all set as light edges.

To simplify the problem, JYY only considers a rooted binary tree with $N$ nodes. These $N$ nodes are numbered from $1$ to $N$. Furthermore, if $u$ has two children with the same $\text{size}(\cdot)$ value, we default the edge between $u$ and its left child to be the heavy edge.

Now, JYY wishes to perform $Q$ additional node deletion operations. Each time, JYY will randomly delete a leaf node from the current binary tree, and you need to dynamically maintain the Heavy-Light Decomposition of this tree.

For ease of output, you only need to output the sum of the values of the nodes pointed to by all heavy edges after each operation. If, after deleting a node, a node $u$ has two children with the same $\text{size}(\cdot)$ value, we maintain the heavy edge partition that $u$ had before the operation was performed.

Input

The first line contains an integer $N$. The next $N$ lines each contain two integers $L_i, R_i$, representing the left child and right child of node $i$, respectively. $L_i = 0$ indicates that node $i$ has no left child, and $R_i = 0$ indicates that node $i$ has no right child. The $(N+2)$-th line contains an integer $Q$, representing the number of deletion operations performed by JYY. The $(N+3)$-th line contains $Q$ space-separated positive integers, representing the IDs of the leaves deleted by JYY. The input data guarantees that each deletion operation removes a leaf node.

Output

Output $Q+1$ lines, each containing an integer representing the sum of the IDs of the nodes pointed to by all heavy edges in the Heavy-Light Decomposition. The first line corresponds to the initial path decomposition, and the subsequent $Q$ lines correspond to the path decomposition after each respective deletion operation.

Examples

Input 1

8
2 3
4 5
0 0
6 7
0 8
0 0
0 0
0 0
7
6 7 8 5 4 2 3

Output 1

20
21
15
7
6
2
3
0

Constraints

For 30% of the data, $N \le 1,000$; For 50% of the data, $N \le 50,000$; For 100% of the data, $N \le 200,000$.