Farmer John discovered that different types of cows like different types of grass. However, he must plant them correctly so as not to harm.
John's farm consists of NN (1≤N≤200,000) fields, and MM pairs of fields are connected by bidirectional paths (1≤M≤200,000). Using these paths, one can go from any field to any other field. Each track has an integer length in the range 1*1,000,000. Any pair of fields is connected by at most one straight path.
In each field, the FD initially planted one of the KK grass types (1≤K≤N). After a while, however, he may decide to change the type of grass in some of the fields. He calls it the "update" operation.
After each update, the FD wants to know the length of the shortest path between two fields with different grass types. That is, among all pairs of fields that have different types of grass, he wants to know which two fields are closest to each other. It is guaranteed that there is always at least one pair of fields with different types of grass.
In 30 percent of the tests, each field is directly connected to no more than 10 lanes.
INPUT FORMAT:
The first input line contains four integers N, M, K, Q, where Q is the number of update operations (1≤Q≤200,000). The next M lines describe the tracks. Each line contains three integers A, B, L indicating that there is a track between fields A, B and its length L. (A, B are integers in the range 1…N). The next line specifies the initial grass type for each field (N integers in the range 1…K). Then there are Q lines, each of which describes one update operation with two integers A and B, meaning that on field A the grass type is changed to B.
OUTPUT FORMAT:
For each update operation, print the length of the shortest path between two fields with different types of grass after applying this update operation.