Почтовая реформа

В Флатландии идет пора реформ. Недавно была проведена реформа дорог, так что теперь по дорогам страны из любого города можно добраться в любой другой, причем только одним способом. Также была проведена реформа волшебников, так что в каждом городе остался ровно один волшебник. Теперь же началась реформа почтовой системы.

Недавно образованное почтовое агентство <<Экс-Федя>> предлагает уникальную услугу --- коллективную посылку. Эта услуга позволяет отправлять посылки жителям всех городов на каком-либо пути по цене обычной посылки. Удивительно, но пользоваться такой услугой стали только волшебники Флатландии, которые стали в большом количестве отправлять друг другу магические кактусы. Агентство столкнулось с непредвиденной проблемой: как известно, все волшебники живут в башнях и мало того, что не строят в них лестницы, так еще время от времени меняют их высоту. Поэтому, чтобы доставить посылку волшебнику, который живет в башне высотой $h$, курьеру агентства требуется иметь с собой не менее $h$ метров веревки.

Вам поручено руководить отделом логистики --- по имеющимся данным о высотах башен и об их изменениях вам нужно определять минимальную длину веревки, которую нужно выдать курьеру, который доставляет посылки между городами $i$ и $j$.

Первая строка входного файла содержит число $n$ --- количество городов в Флатландии ($1 \le n \le 50000$). Во второй строке находится $n$ положительных чисел, не превосходящих $10^5$ --- высоты башен в городах. В следующих $n-1$ строках содержится по два числа $u_i$ и $v_i$ --- описание $i$-й дороги, $1 \le u_i, v_i \le n, u_i \ne v_i$. В следующий строке содержится число $k$ --- количество запросов ($1 \le k \le 100000$). В следующих $k$ строках содержатся описания запросов в следующем формате:

• Уведомление от волшебника из города $i$ о том, что высота его башни стала равна $h$, имеет вид $!$ $i$ $h$, $1 \le i \le n$, $1 \le h \le 10^5$.
• Запрос от курьера о выдаче веревки для доставки посылок во все города на пути от $i$ до $j$ включительно имеет вид $?$ $i$ $j$, $1 \le i, j \le n$.

Для каждого запроса доставки посылок выведите минимальную длину веревки, которую необходимо выдать курьеру.