Croc Champ 2012 - Round 2 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

dfs and similar

trees

*3100

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Archaeology

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThis time you should help a team of researchers on an island in the Pacific Ocean. They research the culture of the ancient tribes that used to inhabit the island many years ago.

Overall they've dug out *n* villages. Some pairs of villages were connected by roads. People could go on the roads in both directions. Overall there were exactly *n* - 1 roads, and from any village one could get to any other one.

The tribes were not peaceful, and they had many wars. As a result of the wars, some villages were completely destroyed. During more peaceful years, some of the villages were restored.

At each moment of time, people used only those roads that belonged to some shortest way between two villages that existed at the given moment. In other words, people used the minimum subset of roads in such a way that it was possible to get from any existing village to any other existing one. Note that throughout the island's whole history, there existed exactly *n* - 1 roads that have been found by the researchers. There never were any other roads.

The researchers think that observing the total sum of used roads' lengths at different moments of time can help to better understand the tribes' culture and answer several historical questions.

You will be given the full history of the tribes' existence. Your task is to determine the total length of used roads at some moments of time.

Input

The first line contains an integer *n* (1 ≤ *n* ≤ 10^{5}) — the number of villages. The next *n* - 1 lines describe the roads. The *i*-th of these lines contains three integers *a*_{i}, *b*_{i}, and *c*_{i} (1 ≤ *a*_{i}, *b*_{i} ≤ *n*, *a*_{i} ≠ *b*_{i}, 1 ≤ *c*_{i} ≤ 10^{9}, 1 ≤ *i* < *n*) — the numbers of villages that are connected by the *i*-th road and the road's length. The numbers in the lines are separated by a space.

The next line contains an integer *q* (1 ≤ *q* ≤ 10^{5}) — the number of queries. Then follow *q* queries, one per line, ordered by time. Each query belongs to one of three types:

- "+
*x*" — village number*x*is restored (1 ≤*x*≤*n*). - "-
*x*" — village number*x*is destroyed (1 ≤*x*≤*n*). - "?" — the archaeologists want to know the total length of the roads which were used for that time period.

It is guaranteed that the queries do not contradict each other, that is, there won't be queries to destroy non-existing villages or restore the already existing ones. It is guaranteed that we have at least one query of type "?". It is also guaranteed that one can get from any village to any other one by the given roads.

At the initial moment of time, no village is considered to exist.

Output

For each query of type "?" print the total length of used roads on a single line. You should print the answers to the queries in the order in which they are given in the input.

Please do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use cin, cout streams, or the %I64d specifier.

Examples

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/22/2024 12:02:05 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|