Компанія Air Glob планує з'єднати повітряним сполученням ~N~ міст країни. Аеропорти перенумеровані від 1 до ~N~ і у ~K~ аеропортах можливі пересадки. Компанія пропонує ~M~ однонаправлених польотів.

Політ ~i~ відбувається з аеропорту ~U_i~ до ~V_i~ з ціною ~D_i~ у.о. Для кожного польоту або в ~U_i~, або в ~V_i~ можлива пересадка. Існує не більше одного польоту між будь якими двома аеропортами в заданому напрямку, і не існує польоту, який починається та закінчується на одному аеропорту.

Авіакомпанія отримала ~Q~ запитів на однонаправлене перевезення туристів. ~І~-й запит - це політ з аеропорту ~A_i~ до ~B_i~. Необхідно визначити, чи можна видати квиток на переліт з ~A_i~ до ~B_i~ та його мінімальну вартість.

Для скорочення виведення інформації ваша програма має вивести загальну кількість квитків, які можна видати, та мінімальну їх сумарну вартість.

Input

Перший рядок містить чотири цілих числа: ~N~, ~M~, ~K~, ~Q~ (~1 \le N \le 20000~, ~1 \le K \le 200, K \le N~, ~1 \le M \le 20000~, ~1 \le Q \le 50000~).

Рядки від 2 до ~M+1~: ~U_i~, ~V_i~, ~D_i~ (~1 \le D_i \le 10000~).

Далі ідуть ~K~ рядків, що містять номери аеропортів із пересадками.

Наступні ~Q~ рядків містять запити на перевезення з ~A_i~ до ~B_i~.

Output

У першому рядку вивести кількість квитків, які можуть бути видані, а у другому - їх сумарну мінімальну вартість.

Scoring

Оцінюється кожен тест окремо.

Sample Input 1

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

Sample Output 1

1
20

Notes

Для першого запиту є тільки один маршрут 1->2->3 з ціною 20. З 3-го аеропорту маршрутів не існує.