JOI-kun on villisika, joka asuu IOI-metsässä, jossa on $N$ ruokintapaikkaa ja $M$ tietä. Ruokintapaikat on numeroitu $1$:stä $N$:ään. $i$-s tie ($1 \le i \le M$) yhdistää ruokintapaikat $A_i$ ja $B_i$ molempiin suuntiin, ja JOI-kunilta kuluu $C_i$ tuntia kulkea tämä tie kumpaan tahansa suuntaan. Mistä tahansa ruokintapaikasta on mahdollista päästä mihin tahansa toiseen ruokintapaikkaan käyttämällä yhtä tai useampaa tietä.

JOI-kun on huono tekemään U-käännöksiä. Hän ei voi tehdä U-käännöstä kesken tien palatakseen ruokintapaikkaan, jossa hän oli. Lisäksi, kun hän saapuu ruokintapaikkaan tietä pitkin, hän ei voi kulkea samaa tietä takaisin palatakseen ruokintapaikkaan, jossa hän oli juuri ennen sitä.

Joka päivä JOI-kun toimittaa ruokaa ruokintapaikkoihin toimitussuunnitelman mukaisesti. Päivän toimitussuunnitelma koostuu $L$ ruokintapaikan jonosta $X_1,X_2,\ldots,X_L$. Hän aloittaa ruoan toimittamisen ruokintapaikasta $X_1$, vierailee ruokintapaikoissa tässä järjestyksessä ja lopettaa toimittamisen ruokintapaikkaan $X_L$. Hän saa kulkea muiden ruokintapaikkojen kautta matkan varrella. On mahdollista, että hänen täytyy toimittaa ruokaa samaan ruokintapaikkaan useita kertoja, mutta $X_j \ne X_{j+1}$ pätee jokaiselle $j$ ($1 \le j \le L-1$). Huomaa, että voi olla olemassa toimitussuunnitelma, jota hän ei pysty toteuttamaan.

Aluksi JOI-kun päättää alkuperäisen toimitussuunnitelman $X_1,X_2,\ldots,X_L$. Hän muuttaa toimitussuunnitelman $P_k$-nnen arvon arvoksi $Q_k$ (eli arvosta $X_{P_k}$ tulee $Q_k$) $k$-nnen päivän ($1 \le k \le T$) aamuna ja toimittaa sitten ruokaa uuden toimitussuunnitelman mukaisesti. On taattua, että $X_j \ne X_{j+1}$ pätee jokaiselle $j$ ($1 \le j \le L-1$) myös muutoksen jälkeen.

Jokaiselle $T$ päivän toimitussuunnitelmalle JOI-kun haluaa selvittää, pystyykö hän toteuttamaan toimitussuunnitelman vai ei, ja jos pystyy, löytää pienimmän mahdollisen ajan ruoan toimittamiseen toimitussuunnitelman mukaisesti.

Tehtävä

Kun IOI-metsän tiedot ja JOI-kunin toimitussuunnitelmat on annettu, kirjoita ohjelma, joka jokaiselle $T$ päivän toimitussuunnitelmalle selvittää, pystyykö hän toteuttamaan toimitussuunnitelman vai ei, ja jos pystyy, löytää pienimmän mahdollisen ajan ruoan toimittamiseen toimitussuunnitelman mukaisesti.

Syöte

Lue seuraavat tiedot vakiosyötteestä.

• Syötteen ensimmäinen rivi sisältää neljä välilyönnillä erotettua kokonaislukua $N$, $M$, $T$ ja $L$. Tämä tarkoittaa, että IOI-metsässä on $N$ ruokintapaikkaa ja $M$ tietä, JOI-kun tarkastelee toimitussuunnitelmia $T$ päivälle ja toimitussuunnitelma koostuu pituuden $L$ jonosta.
• Seuraavien $M$ rivin $i$-s rivi ($1 \le i \le M$) sisältää kolme välilyönnillä erotettua kokonaislukua $A_i$, $B_i$ ja $C_i$. Tämä tarkoittaa, että $i$-s tie yhdistää ruokintapaikat $A_i$ ja $B_i$ molempiin suuntiin, ja JOI-kunilta kuluu $C_i$ tuntia kulkea tämä tie kumpaan tahansa suuntaan.
• Seuraavien $L$ rivin $j$-s rivi ($1 \le j \le L$) sisältää kokonaisluvun $X_j$. Tämä tarkoittaa, että alkuperäinen toimitussuunnitelma on $X_1,X_2,\ldots,X_L$.
• Seuraavien $T$ rivin $k$-s rivi ($1 \le k \le T$) sisältää kaksi välilyönnillä erotettua kokonaislukua $P_k$ ja $Q_k$. Tämä tarkoittaa, että JOI-kun muuttaa toimitussuunnitelman $P_k$-nnen arvon arvoksi $Q_k$ $k$-nnen päivän aamuna.

Tuloste

Kirjoita $T$ riviä vakiotulosteeseen. $k$-nnen rivin ($1 \le k \le T$) tulee sisältää $-1$, jos hän ei pysty toteuttamaan toimitussuunnitelmaa $k$-ntena päivänä, tai pienin mahdollinen toteutusaika tunteina, jos hän pystyy.

Rajoitukset

Kaikki syötetiedot täyttävät seuraavat ehdot.

• $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$).
• Mistä tahansa ruokintapaikasta on mahdollista päästä mihin tahansa toiseen ruokintapaikkaan käyttämällä yhtä tai useampaa tietä.
• $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}$ pätee jokaiselle $j$ ($1 \le j \le L-1$). Myös jokaisen toimitussuunnitelman muutoksen jälkeen $X_j \ne X_{j+1}$ pätee jokaiselle $j$ ($1 \le j \le L-1$).

Osatehtävät

Tehtävässä on 4 osatehtävää. Kunkin osatehtävän pistemäärä ja lisärajoitukset ovat seuraavat:

Osatehtävä 1 [12 pistettä]

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

Osatehtävä 2 [35 pistettä]

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

Osatehtävä 3 [15 pistettä]

• $T=1$.

Osatehtävä 4 [38 pistettä]

Ei lisärajoituksia.

Esimerkit

Syöte 1

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

Tuloste 1

3

Huomautus

Esimerkkisyötteessä 1 alkuperäinen toimitussuunnitelma on $1,2,3$. JOI-kun muuttaa tämän toimitussuunnitelman 3. arvon arvoksi $1$ 1. päivän aamuna. Siksi 1. päivän toimitussuunnitelma on $1,2,1$.

Aluksi JOI-kun toimittaa ruokaa ruokintapaikkaan $1$. Seuraavaksi hän käyttää 1. tietä kulkeakseen ruokintapaikasta $1$ ruokintapaikkaan $2$ ja toimittaa ruokaa ruokintapaikkaan $2$. Sitten hän käyttää 2. tietä kulkeakseen ruokintapaikasta $2$ ruokintapaikkaan $3$. Lopuksi hän käyttää 3. tietä kulkeakseen ruokintapaikasta $3$ ruokintapaikkaan $1$ ja toimittaa ruokaa ruokintapaikkaan $1$. Tällä tavoin toimitussuunnitelman toteuttamiseen kuluu 3 tuntia. Koska tämä on pienin mahdollinen aika, tulosta 3.

Huomaa, että JOI-kun ei voi liikkua ruokintapaikkojen välillä $1 \to 2 \to 1$, koska hän ei voi tehdä U-käännöstä.

Syöte 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

Tuloste 2

5
2
3
-1

Huomautus

Esimerkkisyötteessä 2 1. päivän toimitussuunnitelma on $4,1,4$. Ensin JOI-kun toimittaa ruokaa ruokintapaikkaan $4$. Seuraavaksi hän käyttää 4. tietä kulkeakseen ruokintapaikasta $4$ ruokintapaikkaan $1$ ja toimittaa ruokaa ruokintapaikkaan $1$. Sitten hän käyttää 1., 2., 3. ja 4. tietä tässä järjestyksessä liikkuakseen ruokintapaikkojen välillä $1 \to 2 \to 3 \to 1 \to 4$ ja toimittaa ruokaa ruokintapaikkaan $4$. Tämä vie pienimmän mahdollisen ajan.

1. päivän toimitussuunnitelma on $2,4,2$. Koska JOI-kun ei pysty toteuttamaan tätä toimitussuunnitelmaa, tulosta -1.

Syöte 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

Tuloste 3

38