After landing on Mars surface, scientists found a strange system of caves connected by
tunnels. So they began to research it using remote controlled robots. It was found out that
there exists exactly one route between every pair of caves. But then scientists faced a
particular problem. Sometimes in the caves faint explosions happen. They cause emission
of radioactive isotopes and increase radiation level in the cave. Unfortunately robots
don't stand radiation well. But for the research purposes they must travel from one cave
to another. So scientists placed sensors in every cave to monitor radiation level in the
caves. And now every time they move robots they want to know the maximal radiation level
the robot will have to face during its relocation. So they asked you to write a program that
will solve their problem.
The first line of the input contains one integer N (1 ≤ N ≤ 100000) — the
number of caves. Next N − 1 lines describe tunnels. Each of these lines contains a pair of integers
ai, bi (1 ≤ ai, bi ≤ N)
specifying the numbers of the caves connected by corresponding tunnel. The next line has an integer Q
(Q ≤ 100000) representing the number of queries. The Q queries follow on a single line each. Every query has
a form of "C U V", where C is a single character and can be either 'I' or 'G' representing the type of the query (quotes
for clarity only). In the case of an 'I' query radiation level in U-th cave (1 ≤ U ≤ N) is incremented by V (0 ≤ V ≤ 10000).
In the case of a 'G' query your program must output the maximal level of radiation on the way between caves with
numbers U and V (1 ≤ U, V ≤ N) after all increases of radiation ('I' queries) specified before current query.
It is assumed that initially radiation level is 0 in all caves, and it never decreases with time (because isotopes'
half-life time is much larger than the time of observations).
For every 'G' query output one line containing the maximal radiation level by itself.
I 1 1
G 1 1
G 3 4
I 2 3
G 1 1
G 3 4
Источник задачи: Novosibirsk SU Contest. Petrozavodsk training camp, September 2007