给定一棵带权树。

考虑一个顶点集合 $A$，它是树中顶点的一个子集。初始时，$A$ 为空，我们需要处理一系列查询，每次查询要求向 $A$ 中添加一个顶点或从 $A$ 中移除一个顶点。

在每次查询后，求包含 $A$ 中所有顶点的最小子树的权值。我们将子树的权值定义为其所有边的权值之和。

输入格式

第一行包含一个整数 $n$：树的大小（$1 \le n \le 3 \cdot 10^5$）。

接下来的 $n - 1$ 行描述树的边。每条边描述为 “$u\ v\ w$”：其端点和权值（$1 \le u, v \le n, u \neq v, 0 \le w \le 10^9$）。保证给定的边构成一棵树。

接下来一行包含一个整数 $q$：查询的数量（$1 \le q \le 3 \cdot 10^5$）。

接下来的 $q$ 行包含查询。每个查询给出为 “$t\ v$”，其中 $t$ 为 “+”（向 $A$ 中添加顶点）或 “-”（从 $A$ 中移除顶点），$v$ 为顶点的编号（$1 \le v \le n$）。保证不会要求添加已经在 $A$ 中的顶点，也不会要求移除当前不在 $A$ 中的顶点。

输出格式

输出 $q$ 个数字：每次查询后包含 $A$ 中所有顶点的最小子树的权值。若 $A$ 为空，则输出 0。

样例

输入 1

5
1 2 1
2 3 10
3 4 100
3 5 1000
8
+ 2
+ 5
+ 4
- 5
+ 1
- 4
- 2
- 1

输出 1

0
1010
1110
110
111
1
0
0