Зміна трави
Фермер Джон виявив, що різні типи корів віддають перевагу різним типам трави. Однак, він повинен висаджувати їх правильно, щоб уникнути проблем.
Ферма Джона складається з n полів, і m пар полів з'єднані двонаправленими доріжками. Використовуючи ці доріжки, можна дістатися з будь-якого поля до будь-якого іншого. Кожна доріжка має цілу довжину в межах від 1 до 10^6. Будь-яка пара полів з'єднана не більше ніж однією прямою доріжкою.
На кожному полі Джон спочатку посадив один з k типів трави. Проте з часом він може вирішити змінити тип трави на деяких полях. Він називає це "оновленням".
Після кожного оновлення Джон хоче знати довжину найкоротшого шляху між двома полями, що мають різні типи трави. Тобто, серед усіх пар полів з різними типами трави, він хоче дізнатися, які два поля найближчі один до одного. Гарантується, що завжди існує принаймні одна пара полів з різними типами трави.
Вхідні дані
Перший рядок містить чотири цілі числа n (1 ≤ n ≤ 200000), m (1 ≤ m ≤ 200000), k (1 ≤ k ≤ n), q, де q (1 ≤ q ≤ 200000) - кількість операцій оновлення. Наступні m рядків описують доріжки. Кожен рядок містить три цілі числа a, b, l, що вказують на доріжку між полями a і b з довжиною l (a, b - цілі числа в межах від 1 до n). Наступний рядок вказує початковий тип трави для кожного поля (n цілих чисел в межах від 1 до k). Потім йдуть q рядків, кожен з яких описує одну операцію оновлення двома цілими числами a і b, що означають, що на полі a тип трави змінено на b.
Вихідні дані
Для кожної операції оновлення виведіть довжину найкоротшого шляху між двома полями з різними типами трави після застосування цієї операції оновлення.