JOI-kun è un cinghiale che vive nella Foresta IOI, nella quale ci sono $N$ stazioni di ristoro e $M$ strade. Le stazioni di ristoro sono numerate da $1$ a $N$. La $i$-esima strada ($1 \le i \le M$) collega le stazioni di ristoro $A_i$ e $B_i$ in entrambe le direzioni, e JOI-kun impiega $C_i$ ore per percorrere questa strada in ciascuna direzione. È possibile andare da qualsiasi stazione di ristoro a qualsiasi altra utilizzando una o più strade.

JOI-kun non è bravo a fare inversione a U. Non può fare inversione a U a metà di una strada per tornare alla stazione di ristoro in cui si trovava. Inoltre, quando arriva a una stazione di ristoro utilizzando una strada, non può percorrere quella stessa strada per tornare alla stazione di ristoro in cui si trovava subito prima.

Ogni giorno, JOI-kun rifornisce di cibo le stazioni di ristoro secondo il piano di rifornimento. Il piano di rifornimento per un giorno consiste in una sequenza di $L$ stazioni di ristoro $X_1,X_2,\ldots,X_L$. Egli inizia il rifornimento alla stazione di ristoro $X_1$, visita le stazioni di ristoro in questo ordine e termina il rifornimento alla stazione di ristoro $X_L$. Gli è consentito passare attraverso altre stazioni di ristoro lungo il tragitto. È possibile che debba rifornire una stessa stazione di ristoro più volte, ma vale $X_j \ne X_{j+1}$ per ogni $j$ ($1 \le j \le L-1$). Nota che potrebbe esistere un piano di rifornimento che egli non può eseguire.

All'inizio, JOI-kun determina il piano di rifornimento iniziale $X_1,X_2,\ldots,X_L$. La mattina del $k$-esimo giorno ($1 \le k \le T$) egli cambierà il $P_k$-esimo valore del piano di rifornimento in $Q_k$ (cioè $X_{P_k}$ diventa $Q_k$), e poi rifornirà il cibo secondo il nuovo piano di rifornimento. Si garantisce che $X_j \ne X_{j+1}$ vale per ogni $j$ ($1 \le j \le L-1$) anche dopo la modifica.

Per ciascun piano di rifornimento dei $T$ giorni, JOI-kun vuole determinare se può eseguire il piano di rifornimento o meno e, in caso affermativo, trovare il minimo tempo possibile per rifornire il cibo secondo il piano di rifornimento.

Compito

Dati i dati della Foresta IOI e i piani di rifornimento di JOI-kun, per ciascun piano di rifornimento dei $T$ giorni, scrivi un programma che determini se egli può eseguire il piano di rifornimento o meno e, in caso affermativo, trovi il minimo tempo possibile per rifornire il cibo secondo il piano di rifornimento.

Input

Leggi i seguenti dati dallo standard input.

• La prima riga dell'input contiene quattro interi separati da spazio $N$, $M$, $T$ e $L$. Ciò significa che ci sono $N$ stazioni di ristoro e $M$ strade nella Foresta IOI, JOI-kun considera piani di rifornimento per $T$ giorni, e il piano di rifornimento consiste in una sequenza di lunghezza $L$.
• La $i$-esima riga ($1 \le i \le M$) delle seguenti $M$ righe contiene tre interi separati da spazio $A_i$, $B_i$ e $C_i$. Ciò significa che la $i$-esima strada collega le stazioni di ristoro $A_i$ e $B_i$ in entrambe le direzioni, e JOI-kun impiega $C_i$ ore per percorrere questa strada in ciascuna direzione.
• La $j$-esima riga ($1 \le j \le L$) delle seguenti $L$ righe contiene un intero $X_j$. Ciò significa che il piano di rifornimento iniziale è $X_1,X_2,\ldots,X_L$.
• La $k$-esima riga ($1 \le k \le T$) delle seguenti $T$ righe contiene due interi separati da spazio $P_k$ e $Q_k$. Ciò significa che JOI-kun cambierà il $P_k$-esimo valore del piano di rifornimento in $Q_k$ la mattina del $k$-esimo giorno.

Output

Scrivi $T$ righe sullo standard output. La $k$-esima riga ($1 \le k \le T$) deve contenere $-1$ se egli non può eseguire il piano di rifornimento il $k$-esimo giorno, oppure il minimo tempo possibile in ore per eseguirlo se può.

Limitazioni

Tutti i dati di input soddisfano le seguenti condizioni.

• $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$).
• È possibile andare da qualsiasi stazione di ristoro a qualsiasi altra utilizzando una o più strade.
• $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$).
• Vale $X_j \ne X_{j+1}$ per ogni $j$ ($1 \le j \le L-1$). Inoltre, dopo ogni modifica del piano di rifornimento, vale $X_j \ne X_{j+1}$ per ogni $j$ ($1 \le j \le L-1$).

Subtask

Ci sono 4 subtask. Il punteggio e le limitazioni aggiuntive di ciascun subtask sono i seguenti:

Subtask 1 [12 punti]

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

Subtask 2 [35 punti]

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

Subtask 3 [15 punti]

• $T=1$.

Subtask 4 [38 punti]

Non ci sono limitazioni aggiuntive.

Esempi

Input 1

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

Output 1

3

Nota

Nell'Input di esempio 1, il piano di rifornimento iniziale è $1,2,3$. JOI-kun cambia il 3° valore di questo piano di rifornimento in $1$ la mattina del 1° giorno. Pertanto, il piano di rifornimento del 1° giorno è $1,2,1$.

All'inizio, JOI-kun rifornirà il cibo alla stazione di ristoro $1$. Successivamente, userà la 1ª strada per andare dalla stazione di ristoro $1$ alla stazione di ristoro $2$ e rifornirà il cibo alla stazione di ristoro $2$. Poi, userà la 2ª strada per andare dalla stazione di ristoro $2$ alla stazione di ristoro $3$. Infine, userà la 3ª strada per andare dalla stazione di ristoro $3$ alla stazione di ristoro $1$ e rifornirà il cibo alla stazione di ristoro $1$. In questo modo, ci vorranno 3 ore per eseguire il piano di rifornimento. Poiché questo è il minimo tempo possibile, stampa 3.

Nota che JOI-kun non può muoversi lungo le stazioni di ristoro $1 \to 2 \to 1$ perché non può fare inversione a U.

Input 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

Output 2

5
2
3
-1

Nota

Nell'Input di esempio 2, il piano di rifornimento del 1° giorno è $4,1,4$. Prima, JOI-kun effettuerà il rifornimento alla stazione di ristoro $4$. Successivamente, userà la 4ª strada per andare dalla stazione di ristoro $4$ alla stazione di ristoro $1$ e rifornirà il cibo alla stazione di ristoro $1$. Poi, userà la 1ª, la 2ª, la 3ª e la 4ª strada in quest'ordine per muoversi lungo le stazioni di ristoro $1 \to 2 \to 3 \to 1 \to 4$ e rifornire il cibo alla stazione di ristoro $4$. Questo richiede il minimo tempo possibile.

Il piano di rifornimento del 4° giorno è $2,4,2$. Poiché JOI-kun non può eseguire questo piano di rifornimento, stampa -1.

Input 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

Output 3

38