Зміна трави#10530
Фермер Джон виявив, що різні породи корів надають перевагу різним видам трави. Проте траву необхідно висаджувати обережно, щоб не завдати шкоди коровам.
Ферма Джона складається з полів, і пар полів з'єднані двонаправленими дорогами. За цими дорогами можна дістатися з будь-якого поля до будь-якого іншого. Довжина кожної дороги — ціле число від до 10^6 включно. Між будь-якою парою полів існує не більше однієї прямої дороги.
Спочатку Фермер Джон висаджує на кожному полі один з видів трави. Згодом він може змінювати вид трави, що росте на деяких полях. Така операція називається оновленням.
Після кожного оновлення Фермер Джон хоче дізнатися довжину найкоротшого шляху між двома полями, на яких росте різні види трави. Іншими словами, серед усіх пар полів з різними видами трави він хоче знайти мінімально можливу відстань між ними. Гарантується, що в будь-який момент існує хоча б одна пара полів з різними видами трави.
У першому рядку містяться чотири цілих числа: n~(1 \le n \le 2 \cdot 10^5), m~(1 \le m \le 2 \cdot 10^5), k~(1 \le k \le n) та q~(1 \le q \le 2 \cdot 10^5), де — кількість операцій оновлення.
Наступні рядків описують дороги. Кожен рядок містить три цілих числа та , що означають, що поля та з'єднані двонаправленою дорогою довжини , де 1 \le a, b \le n.
У наступному рядку містяться цілих чисел, що описують початковий вид трави на кожному полі. Кожне значення знаходиться в діапазоні від до .
Наступні рядків описують операції оновлення. Кожен рядок містить два цілих числа та , що означають, що вид трави на полі змінюється на .
Для кожної операції оновлення виведіть довжину найкоротшого шляху між двома полями з різними видами трави після виконання відповідного оновлення.
Приклад 1