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$。像其他合理的航空公司一样，每个航班的 $u_i$、$v_i$ 至少一个是枢纽。任意方向上两农场间至多一个直达航班，没有航班起终点相同。

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