JOI-kun ist ein Wildschwein, das im IOI Forest lebt. Dort gibt es $N$ Futterstellen und $M$ Wege. Die Futterstellen sind von $1$ bis $N$ nummeriert. Der $i$-te Weg ($1\le i\le M$) verbindet die Futterstellen $A_i$ und $B_i$ in beiden Richtungen. JOI-kun benötigt in jeder Richtung $C_i$ Stunden, um diesen Weg zurückzulegen. Jede Futterstelle ist von jeder anderen über einen oder mehrere Wege erreichbar.

JOI-kun kann schlecht umkehren. Er kann nicht mitten auf einem Weg umkehren, um zu der Futterstelle zurückzukehren, von der er gekommen ist. Wenn er über einen Weg an einer Futterstelle ankommt, kann er außerdem nicht auf demselben Weg zu der Futterstelle zurückgehen, an der er unmittelbar zuvor war.

Jeden Tag bringt JOI-kun nach einem Versorgungsplan Futter zu den Futterstellen. Der Versorgungsplan eines Tages besteht aus einer Folge von $L$ Futterstellen $X_1,X_2,\ldots,X_L$. Er beginnt die Versorgung an der Futterstelle $X_1$, besucht die Futterstellen in dieser Reihenfolge und beendet die Versorgung an der Futterstelle $X_L$. Unterwegs darf er andere Futterstellen passieren. Eine Futterstelle kann im Versorgungsplan mehrfach vorkommen, aber für jedes $j$ ($1\le j\le L-1$) gilt $X_j\ne X_{j+1}$. Beachte, dass es Versorgungspläne geben kann, die er nicht ausführen kann.

Zu Beginn legt JOI-kun den anfänglichen Versorgungsplan $X_1,X_2,\ldots,X_L$ fest. Am Morgen des $k$-ten Tages ($1\le k\le T$) ändert er den $P_k$-ten Wert des Versorgungsplans in $Q_k$ (also wird $X_{P_k}$ zu $Q_k$). Anschließend verteilt er das Futter nach dem neuen Versorgungsplan. Es ist garantiert, dass auch nach der Änderung für jedes $j$ ($1\le j\le L-1$) die Bedingung $X_j\ne X_{j+1}$ gilt.

Für jeden Versorgungsplan der $T$ Tage möchte JOI-kun wissen, ob er ihn ausführen kann, und falls ja, wie viel Zeit er dafür mindestens benötigt.

Aufgabe

Schreibe ein Programm, das anhand der Daten des IOI Forest und der Versorgungspläne von JOI-kun für jeden Versorgungsplan der $T$ Tage bestimmt, ob er ihn ausführen kann, und falls ja, die dafür benötigte Mindestzeit ermittelt.

Eingabe

Lies die folgenden Daten von der Standardeingabe.

• Die erste Zeile enthält vier durch Leerzeichen getrennte ganze Zahlen $N$, $M$, $T$ und $L$. Im IOI Forest gibt es $N$ Futterstellen und $M$ Wege, JOI-kun betrachtet Versorgungspläne für $T$ Tage, und der Versorgungsplan ist eine Folge der Länge $L$.
• Die $i$-te der folgenden $M$ Zeilen ($1\le i\le M$) enthält drei durch Leerzeichen getrennte ganze Zahlen $A_i$, $B_i$ und $C_i$. Der $i$-te Weg verbindet die Futterstellen $A_i$ und $B_i$ in beiden Richtungen, und JOI-kun benötigt in jeder Richtung $C_i$ Stunden, um ihn zurückzulegen.
• Die $j$-te der folgenden $L$ Zeilen ($1\le j\le L$) enthält eine ganze Zahl $X_j$. Der anfängliche Versorgungsplan ist $X_1,X_2,\ldots,X_L$.
• Die $k$-te der folgenden $T$ Zeilen ($1\le k\le T$) enthält zwei durch Leerzeichen getrennte ganze Zahlen $P_k$ und $Q_k$. JOI-kun ändert am Morgen des $k$-ten Tages den $P_k$-ten Wert des Versorgungsplans in $Q_k$.

Ausgabe

Gib $T$ Zeilen auf der Standardausgabe aus. Die $k$-te Zeile ($1\le k\le T$) soll -1 enthalten, wenn er den Versorgungsplan des $k$-ten Tages nicht ausführen kann, andernfalls die dafür benötigte Mindestzeit in Stunden.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

• $2\le N\le 2\,000$.
• $N-1\le M\le 2\,000$.
• $1\le T\le 100\,000$.
• $2\le L\le 100\,000$.
• $1\le A_i<B_i\le N$ ($1\le i\le M$).
• $(A_i,B_i)\ne(A_j,B_j)$ ($1\le i<j\le M$).
• Jede Futterstelle ist von jeder anderen über einen oder mehrere Wege erreichbar.
• $1\le C_i\le 1\,000\,000\,000$ ($1\le i\le M$).
• $1\le X_j\le N$ ($1\le j\le L$).
• $1\le P_k\le L$ ($1\le k\le T$).
• $1\le Q_k\le N$ ($1\le k\le T$).
• Für jedes $j$ ($1\le j\le L-1$) gilt $X_j\ne X_{j+1}$. Auch nach jeder Änderung des Versorgungsplans gilt für jedes $j$ ($1\le j\le L-1$) die Bedingung $X_j\ne X_{j+1}$.

Teilaufgaben

Es gibt 4 Teilaufgaben. Die Punktzahlen und zusätzlichen Beschränkungen lauten wie folgt:

Teilaufgabe 1 [12 Punkte]

• $N\le 10$.
• $M\le 10$.
• $T=1$.
• $L\le 10$.
• $C_i\le 10$ ($1\le i\le M$).

Teilaufgabe 2 [35 Punkte]

• $N\le 500$.
• $M\le 500$.
• $T=1$.

Teilaufgabe 3 [15 Punkte]

• $T=1$.

Teilaufgabe 4 [38 Punkte]

Es gibt keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

3 3 1 3
1 2 1
2 3 1
1 3 1
1
2
3
3 1

Ausgabe 1

3

Hinweis

Im ersten Beispiel ist der anfängliche Versorgungsplan $1,2,3$. JOI-kun ändert am Morgen des ersten Tages den dritten Wert dieses Versorgungsplans in $1$. Somit lautet der Versorgungsplan des ersten Tages $1,2,1$.

Zunächst verteilt JOI-kun Futter an Futterstelle $1$. Danach geht er über den ersten Weg von Futterstelle $1$ zu Futterstelle $2$ und verteilt dort Futter. Anschließend geht er über den zweiten Weg von Futterstelle $2$ zu Futterstelle $3$. Schließlich geht er über den dritten Weg von Futterstelle $3$ zu Futterstelle $1$ und verteilt dort Futter. So benötigt er 3 Stunden, um den Versorgungsplan auszuführen. Da dies die Mindestzeit ist, soll 3 ausgegeben werden.

Beachte, dass JOI-kun nicht die Folge von Futterstellen $1\to2\to1$ zurücklegen kann, da er nicht umkehren kann.

Eingabe 2

4 4 4 3
1 2 1
2 3 1
1 3 1
1 4 1
4
1
3
3 4
1 2
3 2
2 4

Ausgabe 2

5
2
3
-1

Hinweis

Im zweiten Beispiel lautet der Versorgungsplan des ersten Tages $4,1,4$. Zuerst verteilt JOI-kun Futter an Futterstelle $4$. Danach geht er über den vierten Weg von Futterstelle $4$ zu Futterstelle $1$ und verteilt dort Futter. Anschließend benutzt er den ersten, zweiten, dritten und vierten Weg in dieser Reihenfolge, um die Futterstellen $1\to2\to3\to1\to4$ zu durchlaufen, und verteilt Futter an Futterstelle $4$. Dies benötigt die geringstmögliche Zeit.

Der Versorgungsplan des vierten Tages lautet $2,4,2$. Da JOI-kun diesen Versorgungsplan nicht ausführen kann, soll -1 ausgegeben werden.

Eingabe 3

5 6 1 5
1 2 8
1 3 8
1 4 8
2 5 2
3 4 6
4 5 6
2
5
1
5
3
5 2

Ausgabe 3

38