What’s this
После посадки на Марс учёные нашли странную систему пещер, соединённых туннелями. И учёные начали исследовать эту систему, используя управляемых роботов. Было обнаружено, что существует ровно один путь между каждой парой пещер. Но потом учёные обнаружили специфическую проблему. Иногда в пещерах происходят небольшие взрывы. Они вызывают выброс радиоактивных изотопов и увеличивают уровень радиации в пещере. К сожалению, роботы плохо выдерживают радиацию. Но для исследования они должны переместиться из одной пещеры в другую. Учёные поместили в каждую пещеру сенсор для мониторинга уровня радиации. Теперь они каждый раз при движении робота хотят знать максимальный уровень радиации, с которым придётся столкнуться роботу во время его перемещения. Как вы уже догадались, программу, которая это делает, будете писать вы.
Формат входных данных
Первая строка содержит одно целое число N (1≤ N ≤ 100000) — количество пещер. Следующие N −1 строк описывают туннели. Каждая из этих строк содержит два целых числа — ai и bi (1 ≤ ai,bi ≤ N), описывыющие туннель из пещеры с номером ai в пещеру с номером bi. Следующая строка содержит целое число Q (1 ≤ Q ≤ 100000), означающее количество запросов. Далее идут Q запросов, по одному на строку. Каждый запрос имеет вид «C U V », где C — символ «I» либо «G», означающие тип запроса (кавычки только для ясности). В случае запроса «I» уровень радиации в U-й пещере (1 ≤ U ≤ N) увеличивается на V (0 ≤ V ≤ 10000). В случае запроса «G» ваша программа должна вывести максимальный уровень радиации на пути между пещерами с номерами U и V (1≤ U,V ≤ N) после всех
увеличений радиации (запросов «I»), указанных ранее. Предполагается, что изначальный уровень радиации равен 0 во всех пещерах, и он никогда не уменьшается со временем (потому что период полураспада изотопов много больше времени наблюдения).
Формат выходных данных
Для каждого запроса «G» выведите одну строкусодержащую максимальный уровень радиации
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2
2 3
2 4
6
I 1 1
G 1 1
G 3 4
I 2 3
G 1 1
G 3 4
|
1
0
1
3
|