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