Description

Adera 是 Microsoft 应用商店中的一款解谜游戏。 异象石是进入 Adera 中异时空的引导物，在 Adera 的异时空中有一张地图。这张地图上有 N 个点，有 N-1 条双向边把它们连通起来。起初地图上没有任何异象石，在接下来的 M 个时刻中，每个时刻会发生以下三种类型的事件之一：
1. 地图的某个点上出现了异象石（已经出现的不会再次出现）；
2. 地图某个点上的异象石被摧毁（不会摧毁没有异象石的点）；
3. 向玩家询问使所有异象石所在的点连通的边集的总长度最小是多少。
请你作为玩家回答这些问题。

Format

Input

第一行有一个整数 N，表示点的个数。
接下来 N-1 行每行三个整数 x,y,z，表示点 x 和 y 之间有一条长度为 z 的双向边。
第 N+1 行有一个正整数 M。
接下来 M 行每行是一个事件，事件是以下三种格式之一：
+ x 表示点 x 上出现了异象石
- x 表示点 x 上的异象石被摧毁
? 表示询问使当前所有异象石所在的点连通所需的边集的总长度最小是多少。

Output

对于每个 ? 事件，输出一个整数表示答案。

Sample 1

Input

6 
1 2 1 
1 3 5 
4 1 7 
4 5 3 
6 4 2 
10 
+ 3 
+ 1 
? 
+ 6 
? 
+ 5 
? 
- 6 
- 3 
? 

Output

5 
14 
17 
10 

Limitation

1s, 128MiB for each test case.

【数据范围与约定 】
对于 30%的数据，1 ≤ n, m ≤ 1000。
对于另 20%的数据，地图是一条链，或者一朵菊花。
对于 100%的数据，1 ≤ n, m ≤ 10^5
, 1 ≤ x, y ≤ n, x ≠ y, 1 ≤ z ≤ 10^9。

Source