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