JOI-kun är ett vildsvin som bor i IOI-skogen, där det finns $N$ matstationer och $M$ vägar. Matstationerna är numrerade från $1$ till $N$. Den $i$:te vägen ($1 \le i \le M$) förbinder matstationerna $A_i$ och $B_i$ i båda riktningarna, och det tar $C_i$ timmar för JOI-kun att gå längs denna väg i endera riktningen. Det är möjligt att ta sig från vilken matstation som helst till vilken annan som helst genom att använda en eller flera vägar.

JOI-kun är dålig på att göra U-svängar. Han kan inte göra en U-sväng halvvägs på en väg för att återvända till den matstation där han var. Dessutom, när han anländer till en matstation via en väg, kan han inte gå längs samma väg för att återvända till den matstation där han nyss var.

Varje dag levererar JOI-kun mat vid matstationer enligt leveransplanen. Leveransplanen för en dag består av en följd av $L$ matstationer $X_1,X_2,\ldots,X_L$. Han börjar leverera vid matstation $X_1$, besöker matstationer i denna ordning och avslutar leveransen vid matstation $X_L$. Han får lov att passera via andra matstationer på vägen. Det är möjligt att han ska leverera vid en matstation flera gånger, men $X_j \ne X_{j+1}$ gäller för varje $j$ ($1 \le j \le L-1$). Observera att det kan finnas en leveransplan som han inte kan utföra.

I början bestämmer JOI-kun den ursprungliga leveransplanen $X_1,X_2,\ldots,X_L$. Han kommer att ändra det $P_k$:te värdet i leveransplanen till $Q_k$ (det vill säga $X_{P_k}$ blir $Q_k$) på morgonen den $k$:te dagen ($1 \le k \le T$), och sedan leverera mat enligt den nya leveransplanen. Det garanteras att $X_j \ne X_{j+1}$ gäller för varje $j$ ($1 \le j \le L-1$) efter ändringen.

För varje leveransplan under de $T$ dagarna vill JOI-kun avgöra om han kan utföra leveransplanen eller inte, och om han kan det, hitta den kortaste möjliga tiden för att leverera mat enligt leveransplanen.

Uppgift

Givet data om IOI-skogen och JOI-kuns leveransplaner, skriv ett program som för varje leveransplan under de $T$ dagarna avgör om han kan utföra leveransplanen eller inte, och om han kan det, hittar den kortaste möjliga tiden för att leverera mat enligt leveransplanen.

Indata

Läs följande data från standard inmatning.

• Den första raden i indatan innehåller fyra mellanslagsseparerade heltal $N$, $M$, $T$ och $L$. Detta betyder att det finns $N$ matstationer och $M$ vägar i IOI-skogen, att JOI-kun betraktar leveransplaner för $T$ dagar, och att leveransplanen består av en följd av längd $L$.
• Den $i$:te raden ($1 \le i \le M$) av de följande $M$ raderna innehåller tre mellanslagsseparerade heltal $A_i$, $B_i$ och $C_i$. Detta betyder att den $i$:te vägen förbinder matstationerna $A_i$ och $B_i$ i båda riktningarna, och att det tar $C_i$ timmar för JOI-kun att gå längs denna väg i endera riktningen.
• Den $j$:te raden ($1 \le j \le L$) av de följande $L$ raderna innehåller ett heltal $X_j$. Detta betyder att den ursprungliga leveransplanen är $X_1,X_2,\ldots,X_L$.
• Den $k$:te raden ($1 \le k \le T$) av de följande $T$ raderna innehåller två mellanslagsseparerade heltal $P_k$ och $Q_k$. Detta betyder att JOI-kun kommer att ändra det $P_k$:te värdet i leveransplanen till $Q_k$ på morgonen den $k$:te dagen.

Utdata

Skriv $T$ rader till standard utmatning. Den $k$:te raden ($1 \le k \le T$) ska innehålla $-1$ om han inte kan utföra leveransplanen den $k$:te dagen, eller den kortaste möjliga tiden i timmar för att utföra den om han kan.

Begränsningar

All indata uppfyller följande villkor.

• $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$).
• Det är möjligt att ta sig från vilken matstation som helst till vilken annan som helst genom att använda en eller flera vägar.
• $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$).
• $X_j \ne X_{j+1}$ gäller för varje $j$ ($1 \le j \le L-1$). Även efter varje ändring av leveransplanen gäller $X_j \ne X_{j+1}$ för varje $j$ ($1 \le j \le L-1$).

Deluppgifter

Det finns 4 deluppgifter. Poängen och de ytterligare begränsningarna för varje deluppgift är följande:

Deluppgift 1 [12 poäng]

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

Deluppgift 2 [35 poäng]

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

Deluppgift 3 [15 poäng]

• $T=1$.

Deluppgift 4 [38 poäng]

Det finns inga ytterligare begränsningar.

Exempel

Indata 1

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

Utdata 1

3

Kommentar

I Exempelindata 1 är den ursprungliga leveransplanen $1,2,3$. JOI-kun ändrar det 3:e värdet i denna leveransplan till $1$ på morgonen den 1:a dagen. Därför är leveransplanen den 1:a dagen $1,2,1$.

Först kommer JOI-kun att leverera mat vid matstation $1$. Därefter kommer han att använda den 1:a vägen för att gå från matstation $1$ till matstation $2$ och leverera mat vid matstation $2$. Sedan kommer han att använda den 2:a vägen för att gå från matstation $2$ till matstation $3$. Slutligen kommer han att använda den 3:e vägen för att gå från matstation $3$ till matstation $1$ och leverera mat vid matstation $1$. På detta sätt tar det 3 timmar att utföra leveransplanen. Eftersom detta är den kortaste möjliga tiden, skriv ut 3.

Observera att JOI-kun inte kan förflytta sig mellan matstationerna $1 \to 2 \to 1$ eftersom han inte kan göra en U-sväng.

Indata 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

Utdata 2

5
2
3
-1

Kommentar

I Exempelindata 2 är leveransplanen den 1:a dagen $4,1,4$. Först kommer JOI-kun att leverera vid matstation $4$. Därefter kommer han att använda den 4:e vägen för att gå från matstation $4$ till matstation $1$ och leverera mat vid matstation $1$. Sedan kommer han att använda den 1:a, 2:a, 3:e och 4:e vägen i denna ordning för att förflytta sig mellan matstationerna $1 \to 2 \to 3 \to 1 \to 4$ och leverera mat vid matstation $4$. Detta tar den kortaste möjliga tiden.

Leveransplanen den 4:e dagen är $2,4,2$. Eftersom JOI-kun inte kan utföra denna leveransplan, skriv ut -1.

Indata 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

Utdata 3

38