涂色游戏（Gra w kolorowanie）的棋盘由 $n$ 个编号为 $1$ 到 $n$ 的格子组成。某些格子之间相邻。棋盘上恰好有 $n-1$ 对相邻格子，且从任意一个格子出发都可以通过相邻格子到达其他任意格子。（因此，棋盘构成一棵树。）

游戏由两名玩家参与。初始时，棋盘上所有格子均为白色，除了一个被涂成红色的格子（属于第一个玩家）和一个被涂成蓝色的格子（属于第二个玩家）。玩家轮流行动。在自己的回合中，玩家选择一个被涂成自己颜色的格子 $u$，然后将一个与 $u$ 相邻的白色格子 $v$ 涂成该颜色。无法行动的玩家输掉游戏。

我们想知道，对于哪些初始格子的选择，第一个玩家拥有必胜策略，即无论第二个玩家如何行动，第一个玩家都能获胜。

具体来说，给定格子集合 $A$ 和 $B$。请编写一个程序，计算有多少对不同的格子 $(a, b)$，使得初始红色格子编号 $a \in A$，初始蓝色格子编号 $b \in B$，且第一个玩家拥有必胜策略。

程序还需要处理集合 $A$ 和 $B$ 的更新。每次更新会向集合 $A$ 或 $B$ 中添加或删除一个格子。请在每次更新后输出满足条件的对数。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 500\,000$)，表示棋盘上的格子数。

接下来的 $n-1$ 行描述棋盘；第 $i$ 行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，表示编号为 $u$ 和 $v$ 的格子相邻。

下一行包含三个整数 $S_A, S_B, q$ ($1 \le S_A, S_B \le n, 0 \le q \le 500\,000$)，分别表示集合 $A$ 的初始大小、集合 $B$ 的初始大小以及更新次数。

下一行包含 $S_A$ 个来自 $\{1, \dots, n\}$ 的不同整数，表示属于集合 $A$ 的格子编号。再下一行包含 $S_B$ 个来自 $\{1, \dots, n\}$ 的不同整数，表示属于集合 $B$ 的格子编号。

接下来的 $q$ 行描述集合的更新；第 $i$ 行包含两个字符 $z, t$ 和一个整数 $w$，由空格分隔 ($z \in \{A, B\}, t \in \{+, -\}, 1 \le w \le n$)。字符 $z$ 表示操作的集合；字符 $t$ 表示操作类型（$+$ 表示添加格子，$ -$ 表示删除格子）；整数 $w$ 表示被添加或删除的顶点编号。你可以假设每次更新都会改变集合（即在执行 $+$ 操作前 $w$ 不在集合中，在执行 $-$ 操作前 $w$ 在集合中）。

在初始状态以及更新过程中，集合 $A$ 和 $B$ 不一定是不相交的。请注意，在统计满足 $a \in A$ 且 $b \in B$ 的格子对 $(a, b)$ 时，必须满足 $a \neq b$。

输出格式

你的程序应输出 $q+1$ 行；第 $i$ 行应包含一个整数，表示在前 $i-1$ 次更新后集合 $A$ 和 $B$ 满足条件的对数。（特别地，第一行应包含初始集合 $A$ 和 $B$ 的对数。）

样例

输入 1

6
1 2
2 3
3 4
3 5
5 6
1 2 1
1
5 6
A + 2

输出 1

1
3

说明 1

初始时 $A = \{1\}$，$B = \{5, 6\}$。我们有两种选择初始格子 $(a, b)$ 的可能：对 $(1, 5)$ 和对 $(1, 6)$。对于对 $(1, 5)$，第一个玩家必须涂色格子 $2$，第二个玩家涂色格子 $3$，第一个玩家无法行动。对于对 $(1, 6)$，第一个玩家涂色格子 $2$，第二个玩家必须涂色格子 $5$，第一个玩家涂色格子 $3$，第二个玩家无法行动。因此，第一个玩家仅在对 $(1, 5)$ 时有必胜策略；故答案为 $1$。

更新集合后，$A = \{1, 2\}$，$B = \{5, 6\}$。第一个玩家在对 $(1, 5), (2, 5)$ 和 $(2, 6)$ 时拥有必胜策略；故答案为 $3$。

子任务

测试集分为以下子任务。每个子任务包含一组或多组测试。 此外，在每个子任务中，至少有一半得分的测试组中 $n$ 为奇数。