После посадки на Марс учёные нашли странную систему пещер, соединённых туннелями. И учёные начали исследовать эту систему, используя управляемых роботов. Было обнаружено, что существует ровно один путь между каждой парой пещер. Но потом учёные обнаружили специфическую проблему. Иногда в пещерах происходят небольшие взрывы. Они вызывают выброс радиоактивных изотопов и увеличивают уровень радиации в пещере. К сожалению, роботы плохо выдерживают радиацию. Но для исследования они должны переместиться из одной пещеры в другую. Учёные поместили в каждую пещеру сенсор для мониторинга уровня радиации. Теперь они каждый раз при движении робота хотят знать максимальный уровень радиации, с которым придётся столкнуться роботу во время его перемещения. Как вы уже догадались, программу, которая это делает, будете писать вы.
Первая строка входного файла содержит одно целое число
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 во всех пещерах, и он никогда не уменьшается со временем (потому что период полураспада изотопов много больше времени наблюдения).
Примеры
входные данные
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