Air Bovinia соединяет $N$ ферм с коровами ($1 \le N \le 200$). Как у любой авиакомпании, $K$ ферм выбраны хабами ($1 \le K \le 100,$ $K \le N$). Фермы имеют номера $1..N$, хабы — $1..K$.

Есть $M$ односторонних рейсов ($1 \le M \le 10,000$). Рейс $i$ идёт из $u_i$ в $v_i$ и стоит $d_i$ долларов ($1 \le d_i \le 1,000,000$).

Получены $Q$ запросов на поездки в одну сторону ($1 \le Q \le 10,000$); запрос $i$ — из $a_i$ в $b_i$. Для пути из $a_i$ в $b_i$ допустима любая последовательность прямых рейсов, даже с повторными посещениями ферм, но нужен хотя бы один хаб, который может быть началом, концом либо промежуточной фермой. Поэтому из $a_i$ в $b_i$ допустимого пути может не быть. Для остальных запросов найдите минимальную стоимость допустимого пути.

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

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

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

• Строки $2+M..1+M+Q$: строка $1+M+i$ описывает запрос $i$ значениями $a_i$ и $b_i$.

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

• Строка $1$: число запросов из $Q$, имеющих допустимый путь.

• Строка $2$: сумма минимальных стоимостей по всем запросам, имеющим допустимый путь.

Примеры

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

3 3 1 3
3 1 10
1 3 10
1 2 7
3 2
2 3
1 2

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

2
24

Примечание

Ферм $3$, номера $1\ldots3$, хаб $1$. Рейс из $3$ в $1$ стоит $10$ и так далее. Запросы: $3\to2$, $2\to3$, $1\to2$.

Единственный путь $3\to2$ стоит $10+7$. Для $2\to3$ пути нет: из фермы $2$ нет рейсов. Единственный допустимый путь $1\to2$ стоит $7$.

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