Фермер Джон обнаружил, что разные типы коров любят разные типы травы. Однако он должен правильно их высаживать, чтобы не навредить.

Ферма Джона состоит из n полей, и m пар полей соединены двунаправленными дорожками. Используя эти дорожки, можно пройти от любого поля к любому другому полю. Каждая дорожка имеет целочисленную длину в интервале 1 .. 106. Любая пара полей соединена не более чем одной прямой дорожкой.

В каждом поле ФД изначально посадил один из 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.

Выходные данные

Для каждой операции обновления выведите длину кратчайшего пути между двумя полями с различными типами травы, после применения этой операции обновления.