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$ מכילה $u_i$, $v_i$, $d_i$ של טיסה $i$.

• שורות $2+M..1+M+Q$: שורה $1+M+i$ מתארת נסיעה $i$ באמצעות $a_i$ ו־$b_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

Note

יש $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