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