Поштова реформа#4328
У Флатландії йде пора реформ. Нещодавно була проведена реформа доріг, так що тепер дорогами країни з довільного міста можна дістатись у довільне інше, причому лише одним способом. Також була проведена реформа чарівників, так що у кожному місті залишився рівно один чарівник. Тепер же почалася реформа поштової системи.
Нещодавно утворене поштове агентство "Екс-Федя" пропонує унікальну послугу — колективну посилку. Ця послуга дозволяє відправляти посилки жителям усіх міст на якомусь шляху за ціною звичайної посилки. Дивно, але користуватись такою послугою стали лише чарівники Флатландії, які стали у великій кількості відправляти один одному магічні кактуси. Агентство зіткнулося з непередбаченою проблемою: як відомо, усі чарівники живуть у баштах і, мало того, що не будують у них сходи, так ще час від часу змінюють їхню висоту. Тому, щоб доставити посилку чарівнику, який живе у башті висотою , кур'єру агентства потрібно мати при собі не менше метрів мотузки.
Вам доручено керувати відділом логістики — за наявними даними про висоти башт та про їх зміни вам потрібно визначати мінімальну довжину мотузки, яку потрібно дати кур'єру, який доставляє посилки між містами та .
Перший рядок вхідного файлу містить число — кількість міст у Флатландії (1 \leq n \leq 50000). У другому рядку знаходяться додатних чисел, які не перевищують 10^5 — висоти башт у містах. У наступних n-1 рядках міститься по два числа u_i та v_i — опис -ї дороги, 1 \leq u_i, v_i \leq n, u_i \neq v_i. У наступному рядку міститься число — кількість запитів (1 \leq k \leq 100000). У наступних рядках містяться описи запитів у такому форматі:
Повідомлення від чарівника з міста про те, що висота його башти стала рівною , має вигляд ! i h, 1 \leq i \leq n, 1 \leq h \leq 10^5.
Запит від кур'єра про видачу мотузки для доставки посилок у всі міста на шляху від до включно має вигляд ? i j, 1 \leq i, j \leq n.
Для кожного запиту про доставку посилок виведіть мінімальну довжину мотузки, яку необхідно видати кур'єру.
Приклад 1