Otların dəyişməsi
Fermer Con, müxtəlif növ inəklərin fərqli ot növlərini sevdiyini öyrəndi. Lakin, otları düzgün əkmək lazımdır ki, zərər verməsin.
Conun ferması n sahədən ibarətdir və m cüt sahə iki istiqamətli yollarla birləşdirilib. Bu yollar vasitəsilə hər hansı bir sahədən digərinə keçmək mümkündür. Hər bir yolun uzunluğu 1 .. 10^6 intervalında tam ədəddir. Hər hansı bir cüt sahə birbaşa yolla ən çox bir dəfə birləşdirilib.
Hər bir sahədə Con əvvəlcə k növ otlardan birini əkdi. Lakin, bir müddət sonra bəzi sahələrdə ot növünü dəyişdirməyə qərar verə bilər. O, bunu "yeniləmə" əməliyyatı adlandırır.
Hər yeniləmədən sonra, Con müxtəlif növ otlara malik iki sahə arasında ən qısa yolun uzunluğunu bilmək istəyir. Yəni, müxtəlif növ otlara malik bütün sahə cütləri arasında, hansı iki sahə bir-birinə ən yaxın olduğunu bilmək istəyir. Həmişə müxtəlif növ otlara malik ən azı bir cüt sahənin olması təmin edilir.
Giriş Məlumatları
Birinci sətir dörd tam ədəd n (1 ≤ n ≤ 200000), m (1 ≤ m ≤ 200000), k (1 ≤ k ≤ n), q, burada q (1 ≤ q ≤ 200000) - yeniləmə əməliyyatlarının sayıdır. Növbəti m sətir yolları təsvir edir. Hər bir sətir üç tam ədəd a, b, l ehtiva edir, bu da a, b sahələri arasında bir yol olduğunu və onun uzunluğunun l olduğunu göstərir (a, b - 1 .. n intervalında tam ədədlərdir). Növbəti sətir hər bir sahə üçün başlanğıc ot növünü göstərir (n tam ədəd 1 .. k intervalında). Sonra q sətir gəlir, hər biri bir yeniləmə əməliyyatını iki tam ədəd a və b ilə təsvir edir, bu da a sahəsində ot növünün b olaraq dəyişdirildiyini göstərir.
Çıxış Məlumatları
Hər yeniləmə əməliyyatı üçün, bu yeniləmə əməliyyatından sonra müxtəlif növ otlara malik iki sahə arasında ən qısa yolun uzunluğunu çıxış edin.