Почтовая реформа
В Флатландии идёт пора реформ. Недавно была проведена реформа дорог, так что теперь по дорогам страны из любого города можно добраться в любой другой, причём только одним сособом. Также была проведена реформа волшебников, так что в каждом городе остался ровно один волшебник. Теперь же началась реформа почтовой системы.
Недавно образованное почтовое агенство "Экс-Федя" предлагает уникальную услугу - коллективную посылку. Эта услуга позволяет отправлять посылки жителям всех городов на каком-либо пути по цене обычной посылки. Удивительно, но пользоваться такой услугой стали только волшебники Флатландии, которые стали в большом количестве отправлять друг другу магические кактусы. Агенство столкнулось с непредвиденной проблемой: как известно, все волшебники живут в башнях и мало того, что не строят в них лестницы, так ещё время от времени меняют их высоту. Поэтому, чтобы доставить посылку волшебнику, который живёт в башне высотой h, курьеру агенства требуется иметь с собой не менее h метров верёвки.
Вам поручено руководить отелом логистики - по имеющимся даным о высотах башен и об их изменениях вам нужно определять минимальную длину верёвки, которую нужно дать курьеру, который доставляет посылки между городами i и j.
Входные данные
Первая строка входного файла содержит число n - количество городов во Флатландии (1 ≤ n ≤ 50000). Во второй строке находится n положительных чисел, не превосходящих 10^5 - высоты башен в городах. В последующих n-1 строках содержится по два числа u_i и v_i - описание i-й дороги, 1 ≤ u_i, v_i ≤ n, u_i ≠ v_i. В следующей строке содержится число k - количество запросов (1 ≤ k ≤ 100000). В следующих k строках содержаться описания запросов в следующем формате:
Уведомление от волшебника из города i о том, что высота его башни стала равной h, имеет вид ! i h,1 ≤ i ≤ n, 1 ≤ h ≤ 10^5.
Запрос от курьера о выдачи верёвки для доставки посылок во все города на пути от i до j включительно имеет вид ? i j, 1 ≤ i, j ≤ n.
Выходные данные
Для каждого запроса доставки посылок выведите минимальную длину верёвки, которую необходимо выдать курьеру.