The coloring game is played on a board consisting of $n$ fields numbered from $1$ to $n$. Some fields are adjacent to others. There are exactly $n - 1$ pairs of adjacent fields, and it is possible to reach any field from any other field by moving between adjacent fields. (Thus, the board forms a tree.)

Two players participate in the game. Initially, all fields on the board are white, except for one field colored red (which belongs to the first player) and one other field colored blue (which belongs to the second player). Players take turns. In their turn, a player chooses any field $u$ colored in their color and then colors one adjacent white field $v$ with that same color. The player who cannot make a move loses the game.

We are interested in determining for which choices of starting fields the first player has a winning strategy, i.e., is able to win the game regardless of the second player's moves.

More specifically, given sets of fields $A$ and $B$, write a program that calculates how many pairs of distinct fields $(a, b)$ exist such that the initial red field $a$ belongs to set $A$, the initial blue field $b$ belongs to set $B$, and the first player has a winning strategy.

The program should also handle updates to sets $A$ and $B$. Each of the $q$ updates adds or removes one field from one of the sets $A$ or $B$. You must output the number of such pairs $(a, b)$ after each update.

Input

The first line of input contains an integer $n$ ($1 \le n \le 500\,000$) — the number of fields on the board.

The next $n - 1$ lines contain the description of the board; the $i$-th of these lines contains two integers $u$ and $v$ ($1 \le u, v \le n$), which mean that fields $u$ and $v$ are adjacent.

The next line contains three integers $S_A$, $S_B$, and $q$ ($1 \le S_A, S_B \le n$, $0 \le q \le 500\,000$) representing, respectively: the initial size of set $A$, the initial size of set $B$, and the number of updates.

The next line contains a sequence of $S_A$ distinct numbers from the set $\{1, \dots, n\}$, representing the numbers of fields belonging to set $A$. The following line contains a sequence of $S_B$ distinct numbers from the set $\{1, \dots, n\}$, representing the numbers of fields belonging to set $B$.

The next $q$ lines contain the description of the set updates; the $i$-th of these lines consists of two characters $z$, $t$ and an integer $w$, separated by single spaces ($z \in \{A, B\}$, $t \in \{+, -\}$, $1 \le w \le n$). The character $z$ denotes the set being operated on; the character $t$ denotes the type of operation (the sign $+$ means adding a field to the set, and the sign $-$ means removing a field from the set); the number $w$ denotes the vertex number being added or removed. You may assume that each update changes the set (i.e., just before the $+$ operation, the field $w$ was not in the set, and just before the $-$ operation, the field $w$ was in the set).

Both initially and during the update process, sets $A$ and $B$ do not have to be disjoint. Recall that in the counted pairs of fields $(a, b)$ such that $a \in A$ and $b \in B$, it must hold that $a \neq b$.

Output

Your program should output exactly $q + 1$ lines; the $i$-th line should contain a single integer representing the number of sought pairs $(a, b)$ for sets $A$ and $B$ after the first $i - 1$ updates. (In particular, the first line should contain the number of pairs for the initial sets $A$ and $B$.)

Note

Explanation of the example: Initially $A = \{1\}$ and $B = \{5, 6\}$. We have two possibilities for choosing the starting fields $(a, b)$: the pair $(1, 5)$ and the pair $(1, 6)$. For the pair $(1, 5)$, the first player must color field $2$, the second player colors field $3$, and the first player cannot make a move. For the pair $(1, 6)$, the first player colors field $2$, the second player must color field $5$, the first player colors field $3$, and the second player cannot make a move. Thus, the first player has a winning strategy only for the pair $(1, 5)$; therefore, the answer is $1$.

After updating the sets, we have $A = \{1, 2\}$ and $B = \{5, 6\}$. The first player has a winning strategy for the pairs $(1, 5)$, $(2, 5)$, and $(2, 6)$; therefore, the answer is $3$.

Subtasks

In each subtask, there are test groups worth at least half the points in total where $n$ is odd.