Air Bovinia соединяет рейсами $N$ ферм, где живут коровы, $1 \le N \le 20,000$. Как у любой авиакомпании, $K$ ферм — узловые: $1 \le K \le 200,$ $K \le N$.

Есть $M$ односторонних рейсов, $1 \le M \le 20,000$. Рейс $i$ из $u_i$ в $v_i$ стоит $d_i$ долларов, $1 \le d_i \le 10{,}000$. Как у разумной авиакомпании, хотя бы один конец каждого рейса узловой. В каждом направлении между парой ферм не более одного прямого рейса, и нет рейсов в ту же ферму.

Bessie управляет билетной службой. Пока она, к сожалению, отсутствовала несколько часов, жуя вкусное сено, поступило $Q$ запросов на отпускные поездки коров в одну сторону, $1 \le Q \le 50,000$, запрос $i$ из $a_i$ в $b_i$.

Помогите перегруженной билетами Bessie определить выполнимость каждого запроса и минимальную стоимость, если он выполним.

Для уменьшения вывода сообщите только общее число выполнимых запросов и их минимальную общую стоимость. Это число может не поместиться в $32$-битное целое.

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

• Строка $1$: целые $N$, $M$, $K$, $Q$.

• Строки $2..M+1$: строка $i+1$ содержит $u_i$, $v_i$, $d_i$; $1 \le u_i,v_i \le N$, $u_i \ne v_i$.

• Строки $M+2..M+K+1$: по одному номеру узловой фермы в $1..N$.

• Строки $M+K+2..M+K+Q+1$: по два числа для запроса из $a_i$ в $b_i$; $1 \le a_i,b_i \le N$, $a_i \ne b_i$.

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

• Строка $1$: число выполнимых запросов.

• Строка $2$: минимальная общая стоимость их выполнения.

Примеры

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

3 3 1 2
1 2 10
2 3 10
2 1 5
2
1 3
3 1

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

1
20

Примечание

Для первого полёта единственный маршрут $1 \to 2 \to 3$ стоит $20$. Из фермы $3$ рейсов нет, и бедные коровы там застряли.

Авторы задачи: Kalki Seksaria и Richard Peng