CF176E Archaeology

This 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 destroyed completely. 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.

The first line contains an integer $ n $ ( $ 1

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 С++. It is preferred to use cin, cout streams or the %I64d specifier.