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\to3$ 无合法路线，因为无航班离开农场 $2$。$1\to2$ 也只有一条合法路线，费用 $7$。

出题人：Kalki Seksaria