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