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$번 줄에 항공편 $i$의 $u_i$, $v_i$, $d_i$.

• $2+M..1+M+Q$번 줄: $1+M+i$번 줄은 $a_i$와 $b_i$으로 $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$에서 나가는 항공편이 없어 $2\to3$은 불가능합니다. $1\to2$의 유일한 유효 경로 비용은 $7$입니다.

문제 출제자: Kalki Seksaria