Печери та тунелі
Після посадки на Марс вчені знайшли дивну систему печер, з'єднаних тунелями. І вчені почали досліджувати цю систему, використовуючи керованих роботів. Було виявлено, що існує рівно один шлях між кожною парою печер. Але потім вчені виявили специфічну проблему. Іноді в печерах відбуваються невеликі вибухи. Вони викликають викид радіоактивних ізотопів і збільшують рівень радіації в печері. На жаль, роботи погано витримують радіацію. Але для дослідження вони повинні переміститись з однієї печери в іншу. Вчені помістили у кожну печеру сенсор для моніторингу рівня радіації. Теперь вони кожен раз при русі робота хочуть знати максимальний рівень радіації, з яким прийдеться зіткнутись роботу під час його переміщення.
Як ви вже здогадались, програму, яка це робить, будете писати ви.
Вхідні дані
Перший рядок вхідного файлу містить одне ціле число 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 виведіть один рядок, який містить максимальний рівень радіації.