Air Bovinia verbindet $N$ Bauernhöfe mit Kühen ($1 \le N \le 200$). Wie andere Fluggesellschaften wählt sie $K$ Drehkreuze ($1 \le K \le 100,$ $K \le N$). Höfe sind $1..N$ nummeriert, Drehkreuze sind $1..K$.

Es gibt $M$ Flüge in eine Richtung ($1 \le M \le 10,000$). Flug $i$ geht von $u_i$ nach $v_i$ und kostet $d_i$ Dollar ($1 \le d_i \le 1,000,000$).

Sie erhält $Q$ Anfragen für einfache Reisen ($1 \le Q \le 10,000$), die $i$-te von $a_i$ nach $b_i$. Von $a_i$ nach $b_i$ darf jede Folge direkter Flüge benutzt werden, auch mit mehrfachen Besuchen, aber mindestens ein Drehkreuz muss vorkommen; dieses kann Start, Ziel oder dazwischen sein. Deshalb kann von $a_i$ nach $b_i$ eine gültige Route fehlen. Für die übrigen Anfragen bestimme die minimalen Kosten einer gültigen Route.

Eingabe

• Zeile $1$: ganze Zahlen $N$, $M$, $K$, $Q$.

• Zeilen $2..1+M$: Zeile $i+1$ enthält $u_i$, $v_i$, $d_i$ für Flug $i$.

• Zeilen $2+M..1+M+Q$: Zeile $1+M+i$ beschreibt Reise $i$ mit $a_i$ und $b_i$.

Ausgabe

• Zeile $1$: Zahl der Anfragen unter $Q$ mit gültiger Route.

• Zeile $2$: Summe der minimalen Kosten aller Anfragen mit gültiger Route.

Beispiele

Eingabe 1

3 3 1 3
3 1 10
1 3 10
1 2 7
3 2
2 3
1 2

Ausgabe 1

2
24

Hinweis

Es gibt $3$ Höfe, nummeriert $1\ldots3$; $1$ ist Drehkreuz. Flug $3$ nach $1$ kostet $10$ usw. Anfragen: $3\to2$, $2\to3$, $1\to2$.

$3\to2$ hat nur eine Route mit Kosten $10+7$. $2\to3$ hat keine, weil kein Flug Hof $2$ verlässt. $1\to2$ hat nur eine gültige Route mit Kosten $7$.

Aufgabenautor: Kalki Seksaria