eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Поштова реформа

Поштова реформа

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

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

Нещодавно утворене поштове агенство "Екс-Федя" пропонує унікальну послугу - колективну посилку. Ця послуга дозволяє відправляти посилки жителям усіх міст на якому-небудь шляху за ціною звичайної посилки. Дивно, але користуватись такою послугою стали лише чарівники Флатландії, які стали у великій кількості відправляти один одному магічні кактуси. Агенство зіткнулось з непередбаченою проблемою: як відомо, усі чарівники живуть в баштах і мало того, що не будують у них сходи, так ще час від часу змінюють їхню висоту. Тому, щоб доставити посилку чарівнику, який живе у башті висотою h, кур'єру агенства потрібно мати при собі не менше h метрів мотузки.

Вам доручено керувати відділом логістики - за наявними даними про висоти башт та про їх зміни вам потрібно визначати мінімальну довину мотузки, яку потрібно дати кур'єру, який доставляє посилки між містами i та j.

Вхідні дані

Перший рядок вхідного файлу містить число n - кількість міст у Флатландії (1n50000). У другому рядку знаходиться n додатних чисел, які не перевищують 10^5 - висоти башт у містах. У наступних n-1 рядках міститься по два числа u_i та v_i - опис i-ї дороги, 1u_i, v_in, u_iv_i. У наступному рядку міститься число k - кількість запитів (1k100000). У настпних k рядках містяться описи запитів у наступному форматі:

  • Повідомлення від чарівника з міста i про те, що висота його башти стала рівною h, має вигляд ! i h, 1in, 1h10^5.

  • Запит від кур'єра про видачу мотузки для доставки посилок у всі міста на шляху від i до j включно має вигляд ? i j, 1i, jn.

Вихідні дані

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

Приклад

Вхідні дані #1
3
1 2 3
1 3
2 3
5
? 1 2
! 1 5
? 2 3
! 3 2
? 1 2
Вихідні дані #1
3
3
5