eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Печери та тунелі

Печери та тунелі

Ліміт часу 5 секунд
Ліміт використання пам'яті 64 MiB

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

Як ви вже здогадались, програму, яка це робить, будете писати ви.

Вхідні дані

Перший рядок вхідного файлу містить одне ціле число N (1N100000) - кількість печер. Наступні N-1 рядків описують тунелі. Кожен з цих рядків містить два цілих числа - a_i та b_i (1a_i, b_iN), які описують тунель з печери з номером a_i у печеру з номером b_i. Наступний рядок містить ціле число Q (1Q100000), яке позначає кількість запитів. Далі йде Q запитів, по одному у рядку. Кожен запит має вид "C U V", де C - символ 'I' або 'G', який позначає тип запиту (лапки лише для ясності).

У випадку запита 'I' рівень радіації у U-й печері (1UN) збільшується на V (0V10000). У випадку запиту 'G' ваша програма повинна вивести максимальний рівень радіації на шляху між печерами з номерами U та V (1U, VN) після усіх збільшень радіації (запитів '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
1
0
1
3