JOI-kun jest dzikiem żyjącym w IOI Forest, gdzie znajduje się $N$ punktów z żywnością i $M$ dróg. Punkty są ponumerowane od $1$ do $N$. $i$-ta droga ($1 \le i \le M$) łączy punkty $A_i$ i $B_i$ w obu kierunkach, a przejście nią w dowolnym kierunku zajmuje JOI-kun $C_i$ godzin. Z każdego punktu można dotrzeć do każdego innego, korzystając z jednej lub większej liczby dróg.

JOI-kun ma trudności z zawracaniem. Nie może zawrócić w połowie drogi, aby wrócić do punktu, z którego przyszedł. Ponadto, gdy dotrze do punktu jakąś drogą, nie może przejść tą samą drogą z powrotem do punktu, w którym był bezpośrednio wcześniej.

Każdego dnia JOI-kun dostarcza żywność do punktów zgodnie z planem dostaw. Plan na jeden dzień jest ciągiem $L$ punktów $X_1,X_2,\ldots,X_L$. Zaczyna dostawy w punkcie $X_1$, odwiedza punkty w tej kolejności i kończy dostawy w punkcie $X_L$. Po drodze może przechodzić przez inne punkty. Może dostarczać żywność do tego samego punktu wielokrotnie, ale dla każdego $j$ ($1 \le j \le L-1$) zachodzi $X_j \ne X_{j+1}$. Zauważ, że mogą istnieć plany dostaw, których nie może wykonać.

Na początku JOI-kun ustala początkowy plan dostaw $X_1,X_2,\ldots,X_L$. Rankiem $k$-tego dnia ($1 \le k \le T$) zmieni $P_k$-tą wartość planu na $Q_k$ (czyli $X_{P_k}$ stanie się $Q_k$), a następnie dostarczy żywność zgodnie z nowym planem. Zagwarantowano, że po zmianie dla każdego $j$ ($1 \le j \le L-1$) zachodzi $X_j \ne X_{j+1}$.

Dla każdego planu dostaw z $T$ dni JOI-kun chce ustalić, czy może go wykonać, a jeśli tak, znaleźć minimalny możliwy czas dostarczenia żywności zgodnie z tym planem.

Zadanie

Mając dane dotyczące IOI Forest oraz planów dostaw JOI-kun, napisz program, który dla każdego planu z $T$ dni ustali, czy można go wykonać, a jeśli tak, znajdzie minimalny możliwy czas dostarczenia żywności zgodnie z tym planem.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

• Pierwszy wiersz wejścia zawiera cztery liczby całkowite $N$, $M$, $T$ i $L$, oddzielone spacjami. Oznacza to, że w IOI Forest jest $N$ punktów z żywnością i $M$ dróg, JOI-kun rozważa plany dostaw na $T$ dni, a plan jest ciągiem długości $L$.
• $i$-ty wiersz ($1 \le i \le M$) z kolejnych $M$ wierszy zawiera trzy liczby całkowite $A_i$, $B_i$ i $C_i$, oddzielone spacjami. Oznacza to, że $i$-ta droga łączy punkty $A_i$ i $B_i$ w obu kierunkach, a przejście nią w dowolnym kierunku zajmuje JOI-kun $C_i$ godzin.
• $j$-ty wiersz ($1 \le j \le L$) z kolejnych $L$ wierszy zawiera liczbę całkowitą $X_j$. Oznacza to, że początkowy plan dostaw to $X_1,X_2,\ldots,X_L$.
• $k$-ty wiersz ($1 \le k \le T$) z kolejnych $T$ wierszy zawiera dwie liczby całkowite $P_k$ i $Q_k$, oddzielone spacją. Oznacza to, że rankiem $k$-tego dnia JOI-kun zmieni $P_k$-tą wartość planu dostaw na $Q_k$.

Wyjście

Wypisz $T$ wierszy na standardowe wyjście. $k$-ty wiersz ($1 \le k \le T$) powinien zawierać -1, jeśli JOI-kun nie może wykonać planu dostaw $k$-tego dnia, albo minimalny możliwy czas jego wykonania w godzinach, jeśli jest to możliwe.

Ograniczenia

Wszystkie dane wejściowe spełniają poniższe warunki.

• $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$).
• Z każdego punktu można dotrzeć do każdego innego, korzystając z jednej lub większej liczby dróg.
• $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$).
• Dla każdego $j$ ($1 \le j \le L-1$) zachodzi $X_j \ne X_{j+1}$. Także po każdej zmianie planu dostaw dla każdego $j$ ($1 \le j \le L-1$) zachodzi $X_j \ne X_{j+1}$.

Podzadania

Są 4 podzadania. Punktacja i dodatkowe ograniczenia każdego podzadania są następujące:

Podzadanie 1 [12 punktów]

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

Podzadanie 2 [35 punktów]

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

Podzadanie 3 [15 punktów]

• $T=1$.

Podzadanie 4 [38 punktów]

Nie ma dodatkowych ograniczeń.

Przykład

Wejście 1

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

Wyjście 1

3

Uwagi

W pierwszym przykładzie początkowy plan dostaw to $1,2,3$. Rankiem pierwszego dnia JOI-kun zmienia trzecią wartość tego planu na $1$. Zatem plan dostaw na pierwszy dzień to $1,2,1$.

Najpierw JOI-kun dostarczy żywność do punktu $1$. Następnie przejdzie pierwszą drogą z punktu $1$ do punktu $2$ i dostarczy żywność do punktu $2$. Potem przejdzie drugą drogą z punktu $2$ do punktu $3$. Na koniec przejdzie trzecią drogą z punktu $3$ do punktu $1$ i dostarczy żywność do punktu $1$. W ten sposób wykonanie planu zajmie 3 godziny. Ponieważ jest to minimalny możliwy czas, należy wypisać 3.

Zauważ, że JOI-kun nie może przejść przez punkty $1 \to 2 \to 1$, ponieważ nie może zawracać.

Wejście 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

Wyjście 2

5
2
3
-1

Uwagi

W drugim przykładzie plan dostaw na pierwszy dzień to $4,1,4$. Najpierw JOI-kun dostarczy żywność do punktu $4$. Następnie przejdzie czwartą drogą z punktu $4$ do punktu $1$ i dostarczy żywność do punktu $1$. Potem przejdzie kolejno pierwszą, drugą, trzecią i czwartą drogą, odwiedzając punkty $1 \to 2 \to 3 \to 1 \to 4$, i dostarczy żywność do punktu $4$. Zajmuje to minimalny możliwy czas.

Plan dostaw na czwarty dzień to $2,4,2$. Ponieważ JOI-kun nie może wykonać tego planu, należy wypisać -1.

Wejście 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

Wyjście 3

38