JOI-kun er et villsvin som bor i IOI-skogen, som har $N$ matstasjoner og $M$ veier. Matstasjonene er nummerert fra $1$ til $N$. Den $i$-te veien ($1 \le i \le M$) forbinder matstasjonene $A_i$ og $B_i$ i begge retninger, og det tar $C_i$ timer for JOI-kun å gå langs denne veien i hver retning. Det er mulig å gå fra en hvilken som helst matstasjon til en hvilken som helst annen ved å bruke én eller flere veier.

JOI-kun er dårlig til å ta U-svinger. Han kan ikke ta en U-sving halvveis på en vei for å vende tilbake til matstasjonen der han var. Dessuten, når han ankommer en matstasjon via en vei, kan han ikke gå langs den samme veien for å vende tilbake til matstasjonen der han var like før.

Hver dag leverer JOI-kun mat ved matstasjoner i henhold til forsyningsplanen. Forsyningsplanen for en dag består av en sekvens av $L$ matstasjoner $X_1,X_2,\ldots,X_L$. Han begynner å levere ved matstasjon $X_1$, besøker matstasjoner i denne rekkefølgen, og avslutter leveringen ved matstasjon $X_L$. Han har lov til å gå via andre matstasjoner underveis. Det er mulig at han skal levere ved en matstasjon flere ganger, men $X_j \ne X_{j+1}$ gjelder for hver $j$ ($1 \le j \le L-1$). Merk at det kan finnes en forsyningsplan som han ikke kan gjennomføre.

I begynnelsen bestemmer JOI-kun den opprinnelige forsyningsplanen $X_1,X_2,\ldots,X_L$. Han vil endre den $P_k$-te verdien i forsyningsplanen til $Q_k$ (det vil si at $X_{P_k}$ blir $Q_k$) om morgenen den $k$-te dagen ($1 \le k \le T$), og deretter levere mat i henhold til den nye forsyningsplanen. Det garanteres at $X_j \ne X_{j+1}$ gjelder for hver $j$ ($1 \le j \le L-1$) etter endringen.

For hver forsyningsplan for de $T$ dagene ønsker JOI-kun å avgjøre om han kan gjennomføre forsyningsplanen eller ikke, og hvis han kan det, finne den korteste mulige tiden for å levere mat i henhold til forsyningsplanen.

Oppgave

Gitt dataene om IOI-skogen og JOI-kuns forsyningsplaner, skriv et program som for hver forsyningsplan for de $T$ dagene avgjør om han kan gjennomføre forsyningsplanen eller ikke, og hvis han kan det, finner den korteste mulige tiden for å levere mat i henhold til forsyningsplanen.

Inndata

Les følgende data fra standard inndata.

• Den første linjen i inndataene inneholder fire heltall $N$, $M$, $T$ og $L$ atskilt med mellomrom. Dette betyr at det er $N$ matstasjoner og $M$ veier i IOI-skogen, at JOI-kun vurderer forsyningsplaner for $T$ dager, og at forsyningsplanen består av en sekvens med lengde $L$.
• Den $i$-te linjen ($1 \le i \le M$) av de følgende $M$ linjene inneholder tre heltall $A_i$, $B_i$ og $C_i$ atskilt med mellomrom. Dette betyr at den $i$-te veien forbinder matstasjonene $A_i$ og $B_i$ i begge retninger, og at det tar $C_i$ timer for JOI-kun å gå langs denne veien i hver retning.
• Den $j$-te linjen ($1 \le j \le L$) av de følgende $L$ linjene inneholder et heltall $X_j$. Dette betyr at den opprinnelige forsyningsplanen er $X_1,X_2,\ldots,X_L$.
• Den $k$-te linjen ($1 \le k \le T$) av de følgende $T$ linjene inneholder to heltall $P_k$ og $Q_k$ atskilt med mellomrom. Dette betyr at JOI-kun vil endre den $P_k$-te verdien i forsyningsplanen til $Q_k$ om morgenen den $k$-te dagen.

Utdata

Skriv $T$ linjer til standard utdata. Den $k$-te linjen ($1 \le k \le T$) skal inneholde $-1$ hvis han ikke kan gjennomføre forsyningsplanen på den $k$-te dagen, eller den korteste mulige tiden i timer for å gjennomføre den hvis han kan.

Begrensninger

Alle inndata oppfyller følgende betingelser.

• $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 er mulig å gå fra en hvilken som helst matstasjon til en hvilken som helst annen ved å bruke én eller flere veier.
• $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}$ gjelder for hver $j$ ($1 \le j \le L-1$). Også etter hver endring av forsyningsplanen gjelder $X_j \ne X_{j+1}$ for hver $j$ ($1 \le j \le L-1$).

Deloppgaver

Det er 4 deloppgaver. Poengsummen og tilleggsbegrensningene for hver deloppgave er som følger:

Deloppgave 1 [12 poeng]

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

Deloppgave 2 [35 poeng]

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

Deloppgave 3 [15 poeng]

• $T=1$.

Deloppgave 4 [38 poeng]

Det er ingen ytterligere begrensninger.

Eksempler

Inndata 1

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

Utdata 1

3

Merk

I Eksempelinndata 1 er den opprinnelige forsyningsplanen $1,2,3$. JOI-kun endrer den 3. verdien i denne forsyningsplanen til $1$ om morgenen den 1. dagen. Derfor er forsyningsplanen på den 1. dagen $1,2,1$.

Først vil JOI-kun levere mat ved matstasjon $1$. Deretter vil han bruke den 1. veien for å gå fra matstasjon $1$ til matstasjon $2$ og levere mat ved matstasjon $2$. Så vil han bruke den 2. veien for å gå fra matstasjon $2$ til matstasjon $3$. Til slutt vil han bruke den 3. veien for å gå fra matstasjon $3$ til matstasjon $1$ og levere mat ved matstasjon $1$. På denne måten vil det ta 3 timer å gjennomføre forsyningsplanen. Siden dette er den korteste mulige tiden, skriv ut 3.

Merk at JOI-kun ikke kan bevege seg mellom matstasjonene $1 \to 2 \to 1$ fordi han ikke kan ta en U-sving.

Inndata 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

Merk

I Eksempelinndata 2 er forsyningsplanen på den 1. dagen $4,1,4$. Først vil JOI-kun levere ved matstasjon $4$. Deretter vil han bruke den 4. veien for å gå fra matstasjon $4$ til matstasjon $1$ og levere mat ved matstasjon $1$. Så vil han bruke den 1., 2., 3. og 4. veien i denne rekkefølgen for å bevege seg mellom matstasjonene $1 \to 2 \to 3 \to 1 \to 4$ og levere mat ved matstasjon $4$. Dette tar den korteste mulige tiden.

Forsyningsplanen på den 4. dagen er $2,4,2$. Siden JOI-kun ikke kan gjennomføre denne forsyningsplanen, skriv ut -1.

Inndata 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