Задача 18539. What's this

After landing on Mars, scientists found a strange system of caves connected by tunnels. And scientists began to explore this system using controlled robots. It was found that there is exactly one path between each pair of caves. But then scientists discovered a specific problem. Sometimes small explosions occur in caves. They cause the release of radioactive isotopes and increase the level of radiation in the cave. Unfortunately, robots do not withstand radiation well. But in order to explore, they must move from one cave to another. The scientists placed a sensor in each cave to monitor the level of radiation.  Now, every time the robot moves, they want to know the maximum level of radiation that the robot will have to face during its movement. As you may have guessed, you will write the program that does this.

The first line of the input file contains a single integer N (1≤ N ≤ 100000) — number of caves. The next N −1 lines describe tunnels. Each of these lines contains two integers — a_i and b_i (1 ≤ a_i, b_i ≤ N) describing the tunnel from the cave with the number a_i to the cave with number b_i. The next line contains an integer Q (1 ≤ Q ≤ 100000) representing the number of requests. Next come Q queries, one per line. Each query is of the form «C U V », where C — character «I» or «G» , indicating the type of request (quotes for clarity only). If requested «I» radiation level in the Uth cave (1 ≤ U ≤ N) increases by V (0 ≤ V ≤ 10000). In the case of  «G» your program should output the maximum radiation level on the path between caves with numbers U and V (1≤ U,V ≤ N) after all
increases in radiation (queries "I"), mentioned earlier. It is assumed that the initial level of radiation is 0 in all caves, and it never decreases with time (because the half-life of isotopes is much longer than the observation time).

Examples