You are given an edge-weighted tree.

Consider a set A which is a subset of vertices of the tree. Initially, A is empty, and we have to process queries which ask to add a vertex to A or remove a vertex from A.

After each query, find the weight of the minimum subtree containing all vertices from A. We define the weight of the subtree as the sum of weights of its edges.

The first line of input contains an integer n: the size of the tree (1 ≤ n ≤ 3 · 10⁵).

The next n−1 lines describe edges of the tree. Each edge is described as “u v w”: its endpoints and weight (1 ≤ u, v ≤ n, u ≠ v, 0 ≤ w ≤ 10⁹). It is guaranteed that the given edges form a tree.

The following line contains an integer q: the number of queries (1 ≤ q ≤ 3 · 10⁵).

The next q lines contain queries. Each query is given as “t v”, where t is either “+” (add vertex to A) or “-” (remove vertex from A), and v is the number of the vertex (1 ≤ v ≤ n). It is guaranteed that you are never asked to add a vertex which is already in A, or to remove a vertex which is not currently in A.

Print q numbers: the weight of the smallest subtree containing all vertices from A after each query. In case A is empty, print a 0.