JOI-kun er villisvín sem býr í IOI-skógi, þar sem eru $N$ fóðurstöðvar og $M$ vegir. Fóðurstöðvarnar eru númeraðar frá $1$ til $N$. $i$-ti vegurinn ($1 \le i \le M$) tengir fóðurstöðvar $A_i$ og $B_i$ í báðar áttir, og það tekur JOI-kun $C_i$ klukkustundir að fara eftir þessum vegi í hvora áttina sem er. Það er hægt að fara frá hvaða fóðurstöð sem er til hvaða annarrar sem er með því að nota einn eða fleiri vegi.

JOI-kun er lélegur í að taka U-beygjur. Hann getur ekki tekið U-beygju á miðjum vegi til að snúa aftur á fóðurstöðina þar sem hann var. Þar að auki, þegar hann kemur á fóðurstöð eftir vegi, getur hann ekki farið eftir þeim vegi til að snúa aftur á fóðurstöðina þar sem hann var rétt áður.

Á hverjum degi dreifir JOI-kun fóðri á fóðurstöðvar samkvæmt dreifingaráætlun. Dreifingaráætlun fyrir dag samanstendur af runu af $L$ fóðurstöðvum $X_1,X_2,\ldots,X_L$. Hann byrjar að dreifa á fóðurstöð $X_1$, heimsækir fóðurstöðvar í þessari röð og endar á að dreifa á fóðurstöð $X_L$. Honum er leyfilegt að fara í gegnum aðrar fóðurstöðvar á leiðinni. Það er mögulegt að hann eigi að dreifa á fóðurstöð oftar en einu sinni, en $X_j \ne X_{j+1}$ gildir fyrir hvert $j$ ($1 \le j \le L-1$). Athugið að það gæti verið til dreifingaráætlun sem hann getur ekki framkvæmt.

Í upphafi ákveður JOI-kun upphaflegu dreifingaráætlunina $X_1,X_2,\ldots,X_L$. Hann mun breyta $P_k$-ta gildinu í dreifingaráætluninni í $Q_k$ (þ.e. $X_{P_k}$ verður $Q_k$) að morgni $k$-ta dagsins ($1 \le k \le T$), og dreifa síðan fóðri samkvæmt nýju dreifingaráætluninni. Það er tryggt að $X_j \ne X_{j+1}$ gildi fyrir hvert $j$ ($1 \le j \le L-1$) eftir breytinguna.

Fyrir hverja dreifingaráætlun fyrir dagana $T$ vill JOI-kun ákvarða hvort hann geti framkvæmt dreifingaráætlunina eða ekki, og ef hann getur það, finna lágmarkstíma sem mögulegur er til að dreifa fóðri samkvæmt dreifingaráætluninni.

Verkefni

Gefið gögnin um IOI-skóg og dreifingaráætlanir JOI-kuns, fyrir hverja dreifingaráætlun fyrir dagana $T$, skrifið forrit sem ákvarðar hvort hann geti framkvæmt dreifingaráætlunina eða ekki, og ef hann getur það, finnur lágmarkstíma sem mögulegur er til að dreifa fóðri samkvæmt dreifingaráætluninni.

Inntak

Lesið eftirfarandi gögn úr staðalinntaki.

• Fyrsta línan í inntakinu inniheldur fjórar heiltölur $N$, $M$, $T$ og $L$ aðskildar með bilum. Þetta þýðir að það eru $N$ fóðurstöðvar og $M$ vegir í IOI-skógi, JOI-kun skoðar dreifingaráætlanir fyrir $T$ daga, og dreifingaráætlunin samanstendur af runu af lengd $L$.
• $i$-ta línan ($1 \le i \le M$) af næstu $M$ línum inniheldur þrjár heiltölur $A_i$, $B_i$ og $C_i$ aðskildar með bilum. Þetta þýðir að $i$-ti vegurinn tengir fóðurstöðvar $A_i$ og $B_i$ í báðar áttir, og það tekur JOI-kun $C_i$ klukkustundir að fara eftir þessum vegi í hvora áttina sem er.
• $j$-ta línan ($1 \le j \le L$) af næstu $L$ línum inniheldur heiltölu $X_j$. Þetta þýðir að upphaflega dreifingaráætlunin er $X_1,X_2,\ldots,X_L$.
• $k$-ta línan ($1 \le k \le T$) af næstu $T$ línum inniheldur tvær heiltölur $P_k$ og $Q_k$ aðskildar með bilum. Þetta þýðir að JOI-kun mun breyta $P_k$-ta gildinu í dreifingaráætluninni í $Q_k$ að morgni $k$-ta dagsins.

Úttak

Skrifið $T$ línur í staðalúttak. $k$-ta línan ($1 \le k \le T$) á að innihalda $-1$ ef hann getur ekki framkvæmt dreifingaráætlunina á $k$-ta deginum, eða lágmarkstímann í klukkustundum til að framkvæma hana ef hann getur það.

Skorður

Öll inntaksgögn uppfylla eftirfarandi skilyrði.

• $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$).
• Það er hægt að fara frá hvaða fóðurstöð sem er til hvaða annarrar sem er með því að nota einn eða fleiri vegi.
• $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}$ gildir fyrir hvert $j$ ($1 \le j \le L-1$). Einnig eftir hverja breytingu á dreifingaráætluninni gildir $X_j \ne X_{j+1}$ fyrir hvert $j$ ($1 \le j \le L-1$).

Undirverkefni

Það eru 4 undirverkefni. Stigagjöf og viðbótarskorður hvers undirverkefnis eru sem hér segir:

Undirverkefni 1 [12 stig]

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

Undirverkefni 2 [35 stig]

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

Undirverkefni 3 [15 stig]

• $T=1$.

Undirverkefni 4 [38 stig]

Það eru engar frekari skorður.

Dæmi

Inntak 1

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

Úttak 1

3

Athugasemd

Í sýnidæmi 1 er upphaflega dreifingaráætlunin $1,2,3$. JOI-kun breytir 3. gildinu í þessari dreifingaráætlun í $1$ að morgni 1. dagsins. Þess vegna er dreifingaráætlunin á 1. deginum $1,2,1$.

Fyrst mun JOI-kun dreifa fóðri á fóðurstöð $1$. Næst mun hann nota 1. veginn til að fara frá fóðurstöð $1$ til fóðurstöðvar $2$ og dreifa fóðri á fóðurstöð $2$. Síðan mun hann nota 2. veginn til að fara frá fóðurstöð $2$ til fóðurstöðvar $3$. Að lokum mun hann nota 3. veginn til að fara frá fóðurstöð $3$ til fóðurstöðvar $1$ og dreifa fóðri á fóðurstöð $1$. Á þennan hátt mun það taka 3 klukkustundir að framkvæma dreifingaráætlunina. Þar sem þetta er lágmarkstíminn sem mögulegur er, skrifið út 3.

Athugið að JOI-kun getur ekki farið á milli fóðurstöðva $1 \to 2 \to 1$ vegna þess að hann getur ekki tekið U-beygju.

Inntak 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

Úttak 2

5
2
3
-1

Athugasemd

Í sýnidæmi 2 er dreifingaráætlunin á 1. deginum $4,1,4$. Fyrst mun JOI-kun dreifa á fóðurstöð $4$. Næst mun hann nota 4. veginn til að fara frá fóðurstöð $4$ til fóðurstöðvar $1$ og dreifa fóðri á fóðurstöð $1$. Síðan mun hann nota 1., 2., 3. og 4. veginn í þessari röð til að fara á milli fóðurstöðva $1 \to 2 \to 3 \to 1 \to 4$ og dreifa fóðri á fóðurstöð $4$. Þetta tekur lágmarkstíma sem mögulegur er.

Dreifingaráætlunin á 4. deginum er $2,4,2$. Þar sem JOI-kun getur ekki framkvæmt þessa dreifingaráætlun, skrifið út -1.

Inntak 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

Úttak 3

38