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 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. 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