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$ です。合理的な航空会社らしく、各便は少なくとも一方の端点がハブです。同じ方向の二農場間は直行便が高々一本で、同じ農場を出発して到着する便はありません。

Bessie は券のサービスを担当します。残念ながらおいしい干し草を数時間噛みに出かけた間に、牛の休暇の片道旅行の依頼 $Q$ 件（$1 \le Q \le 50,000$）を受けました。依頼 $i$ は $a_i$ から $b_i$ です。

券の処理に困っている彼女を助け、各依頼が可能か、可能なら最低費用を求めてください。

出力を減らすため、可能な依頼数とその最低総費用だけを出力します。この数は $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