JOI-kun — дикий кабан, живущий в IOI Forest, где есть $N$ кормовых пунктов и $M$ дорог. Кормовые пункты пронумерованы от $1$ до $N$. Дорога $i$ ($1 \le i \le M$) соединяет кормовые пункты $A_i$ и $B_i$ в обоих направлениях; прохождение этой дороги в любом направлении занимает у JOI-kun $C_i$ часов. Из любого кормового пункта можно добраться до любого другого по одной или нескольким дорогам.

JOI-kun плохо умеет разворачиваться. Он не может развернуться посреди дороги, чтобы вернуться в кормовой пункт, из которого пришёл. Более того, прибыв в кормовой пункт по какой-либо дороге, он не может пойти обратно по этой же дороге в кормовой пункт, где только что находился.

Каждый день JOI-kun доставляет корм в кормовые пункты согласно плану доставки. План доставки на день состоит из последовательности $L$ кормовых пунктов $X_1, X_2, \ldots, X_L$. Он начинает доставку в кормовом пункте $X_1$, посещает кормовые пункты в указанном порядке и заканчивает доставку в кормовом пункте $X_L$. По пути ему разрешается проходить через другие кормовые пункты. Возможно, что ему нужно доставить корм в один пункт несколько раз, но для каждого $j$ ($1 \le j \le L-1$) выполняется $X_j \ne X_{j+1}$. Обратите внимание: могут существовать планы доставки, которые он не может выполнить.

Сначала JOI-kun определяет исходный план доставки $X_1, X_2, \ldots, X_L$. Утром дня $k$ ($1 \le k \le T$) он заменяет значение на позиции $P_k$ в плане доставки на $Q_k$ (то есть $X_{P_k}$ становится равным $Q_k$), а затем доставляет корм согласно новому плану. Гарантируется, что после изменения для каждого $j$ ($1 \le j \le L-1$) выполняется $X_j \ne X_{j+1}$.

Для каждого плана доставки за $T$ дней JOI-kun хочет определить, сможет ли он его выполнить, и, если сможет, найти минимальное время, необходимое для доставки корма по этому плану.

Задание

Даны сведения об IOI Forest и планах доставки JOI-kun. Напишите программу, которая для каждого плана доставки за $T$ дней определяет, сможет ли он его выполнить, и, если сможет, находит минимальное время, необходимое для доставки корма по этому плану.

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

Прочитайте следующие данные из стандартного ввода.

• Первая строка содержит четыре целых числа $N$, $M$, $T$ и $L$, разделённые пробелами. Это означает, что в IOI Forest есть $N$ кормовых пунктов и $M$ дорог, JOI-kun рассматривает планы доставки на $T$ дней, а план доставки представляет собой последовательность длины $L$.
• Строка $i$ ($1 \le i \le M$) из следующих $M$ строк содержит три целых числа $A_i$, $B_i$ и $C_i$, разделённые пробелами. Это означает, что дорога $i$ соединяет кормовые пункты $A_i$ и $B_i$ в обоих направлениях, а прохождение этой дороги в любом направлении занимает у JOI-kun $C_i$ часов.
• Строка $j$ ($1 \le j \le L$) из следующих $L$ строк содержит целое число $X_j$. Это означает, что исходный план доставки имеет вид $X_1, X_2, \ldots, X_L$.
• Строка $k$ ($1 \le k \le T$) из следующих $T$ строк содержит два целых числа $P_k$ и $Q_k$, разделённые пробелами. Это означает, что утром дня $k$ JOI-kun заменит значение на позиции $P_k$ в плане доставки на $Q_k$.

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

Выведите $T$ строк в стандартный вывод. Строка $k$ ($1 \le k \le T$) должна содержать -1, если JOI-kun не может выполнить план доставки в день $k$, или минимальное время его выполнения в часах, если может.

Ограничения

Все входные данные удовлетворяют следующим условиям.

• $2 \le N \le 2\,000$.
• $N-1 \le M \le 2\,000$.
• $1 \le T \le 100\,000$.
• $2 \le L \le 100\,000$.
• $1 \le A_i < B_i \le N$ ($1 \le i \le M$).
• $(A_i,B_i) \ne (A_j,B_j)$ ($1 \le i < j \le M$).
• Из любого кормового пункта можно добраться до любого другого по одной или нескольким дорогам.
• $1 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le M$).
• $1 \le X_j \le N$ ($1 \le j \le L$).
• $1 \le P_k \le L$ ($1 \le k \le T$).
• $1 \le Q_k \le N$ ($1 \le k \le T$).
• Для каждого $j$ ($1 \le j \le L-1$) выполняется $X_j \ne X_{j+1}$. Также после каждого изменения плана доставки для каждого $j$ ($1 \le j \le L-1$) выполняется $X_j \ne X_{j+1}$.

Подзадачи

Всего 4 подзадачи. Баллы и дополнительные ограничения для каждой подзадачи приведены ниже.

Подзадача 1 [12 баллов]

• $N \le 10$.
• $M \le 10$.
• $T = 1$.
• $L \le 10$.
• $C_i \le 10$ ($1 \le i \le M$).

Подзадача 2 [35 баллов]

• $N \le 500$.
• $M \le 500$.
• $T = 1$.

Подзадача 3 [15 баллов]

• $T = 1$.

Подзадача 4 [38 баллов]

Дополнительных ограничений нет.

Примеры

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

3 3 1 3
1 2 1
2 3 1
1 3 1
1
2
3
3 1

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

3

Примечание

В первом примере исходный план доставки — $1,2,3$. Утром первого дня JOI-kun заменяет третье значение в этом плане на $1$. Поэтому план доставки на первый день — $1,2,1$.

Сначала JOI-kun доставит корм в кормовой пункт $1$. Затем он пройдёт по первой дороге из кормового пункта $1$ в кормовой пункт $2$ и доставит туда корм. После этого он пройдёт по второй дороге из кормового пункта $2$ в кормовой пункт $3$. Наконец, он пройдёт по третьей дороге из кормового пункта $3$ в кормовой пункт $1$ и доставит туда корм. Таким образом, выполнение плана займёт $3$ часа. Поскольку это минимальное возможное время, выведите $3$.

Обратите внимание: JOI-kun не может пройти по кормовым пунктам $1 \to 2 \to 1$, поскольку он не может разворачиваться.

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

4 4 4 3
1 2 1
2 3 1
1 3 1
1 4 1
4
1
3
3 4
1 2
3 2
2 4

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

5
2
3
-1

Примечание

Во втором примере план доставки на первый день — $4,1,4$. Сначала JOI-kun доставит корм в кормовой пункт $4$. Затем он пройдёт по четвёртой дороге из кормового пункта $4$ в кормовой пункт $1$ и доставит туда корм. После этого он пройдёт по первой, второй, третьей и четвёртой дорогам именно в таком порядке, посетив кормовые пункты $1 \to 2 \to 3 \to 1 \to 4$, и доставит корм в кормовой пункт $4$. Это занимает минимальное возможное время.

План доставки на четвёртый день — $2,4,2$. Поскольку JOI-kun не может выполнить этот план, выведите -1.

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

5 6 1 5
1 2 8
1 3 8
1 4 8
2 5 2
3 4 6
4 5 6
2
5
1
5
3
5 2

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

38