JOI-kun adalah seekor babi hutan yang tinggal di IOI Forest, yang memiliki $N$ tempat makanan dan $M$ jalan. Tempat makanan diberi nomor $1$ hingga $N$. Jalan ke-$i$ ($1 \le i \le M$) menghubungkan tempat makanan $A_i$ dan $B_i$ dalam kedua arah, dan JOI-kun memerlukan $C_i$ jam untuk melewati jalan ini dalam arah mana pun. Setiap tempat makanan dapat dicapai dari tempat makanan lainnya melalui satu atau beberapa jalan.

JOI-kun tidak pandai berbalik arah. Ia tidak dapat berbalik di tengah jalan untuk kembali ke tempat makanan asalnya. Selain itu, setelah tiba di sebuah tempat makanan melalui suatu jalan, ia tidak boleh langsung melewati jalan tersebut untuk kembali ke tempat makanan sebelumnya.

Setiap hari, JOI-kun memasok makanan sesuai dengan rencana pasokan. Rencana untuk satu hari berupa urutan $L$ tempat makanan $X_1,X_2,\ldots,X_L$. Ia mulai memasok di $X_1$, mengunjungi tempat makanan sesuai urutan tersebut, dan selesai di $X_L$. Di tengah perjalanan, ia boleh melewati tempat makanan lain. Suatu tempat makanan boleh menjadi tujuan pasokan beberapa kali, tetapi $X_j \ne X_{j+1}$ untuk setiap $j$ ($1 \le j \le L-1$). Perhatikan bahwa mungkin ada rencana pasokan yang tidak dapat ia laksanakan.

Pada awalnya, JOI-kun menentukan rencana pasokan awal $X_1,X_2,\ldots,X_L$. Pada pagi hari ke-$k$ ($1 \le k \le T$), ia mengubah nilai ke-$P_k$ dalam rencana menjadi $Q_k$, yaitu $X_{P_k}$ menjadi $Q_k$, lalu memasok makanan sesuai rencana baru. Dijamin bahwa setelah perubahan, $X_j \ne X_{j+1}$ untuk setiap $j$ ($1 \le j \le L-1$).

Untuk setiap rencana selama $T$ hari, JOI-kun ingin mengetahui apakah rencana dapat dilaksanakan dan, jika bisa, waktu minimum untuk memasok makanan sesuai rencana tersebut.

Tugas

Diberikan data IOI Forest dan rencana pasokan JOI-kun, tulislah program yang, untuk setiap rencana selama $T$ hari, menentukan apakah rencana dapat dilaksanakan dan, jika bisa, menghitung waktu minimum untuk memasok makanan sesuai rencana tersebut.

Masukan

Bacalah data berikut dari masukan standar.

• Baris pertama berisi empat bilangan bulat yang dipisahkan spasi, $N$, $M$, $T$, dan $L$. Ini berarti terdapat $N$ tempat makanan dan $M$ jalan di IOI Forest, JOI-kun mempertimbangkan rencana selama $T$ hari, dan rencana berupa urutan sepanjang $L$.
• Baris ke-$i$ ($1 \le i \le M$) dari $M$ baris berikutnya berisi tiga bilangan bulat yang dipisahkan spasi, $A_i$, $B_i$, dan $C_i$. Ini berarti jalan ke-$i$ menghubungkan tempat makanan $A_i$ dan $B_i$ dalam kedua arah, dan JOI-kun memerlukan $C_i$ jam untuk melewatinya dalam arah mana pun.
• Baris ke-$j$ ($1 \le j \le L$) dari $L$ baris berikutnya berisi bilangan bulat $X_j$. Ini berarti rencana pasokan awal adalah $X_1,X_2,\ldots,X_L$.
• Baris ke-$k$ ($1 \le k \le T$) dari $T$ baris berikutnya berisi dua bilangan bulat yang dipisahkan spasi, $P_k$ dan $Q_k$. Ini berarti JOI-kun mengubah nilai ke-$P_k$ dalam rencana menjadi $Q_k$ pada pagi hari ke-$k$.

Keluaran

Tuliskan $T$ baris ke keluaran standar. Baris ke-$k$ ($1 \le k \le T$) harus berisi -1 jika rencana hari ke-$k$ tidak dapat dilaksanakan, atau waktu minimum dalam jam untuk melaksanakannya jika bisa.

Batasan

Semua data masukan memenuhi kondisi berikut.

• $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$).
• Setiap tempat makanan dapat dicapai dari tempat makanan lainnya melalui satu atau beberapa jalan.
• $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}$ untuk setiap $j$ ($1 \le j \le L-1$). Setelah setiap perubahan rencana, kondisi $X_j \ne X_{j+1}$ juga berlaku untuk setiap $j$ ($1 \le j \le L-1$).

Subsoal

Terdapat 4 subsoal. Nilai dan batasan tambahan masing-masing subsoal adalah sebagai berikut:

Subsoal 1 [12 poin]

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

Subsoal 2 [35 poin]

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

Subsoal 3 [15 poin]

• $T=1$.

Subsoal 4 [38 poin]

Tidak ada batasan tambahan.

Contoh

Masukan 1

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

Keluaran 1

3

Penjelasan

Pada contoh 1, rencana awal adalah $1,2,3$. Pada pagi hari pertama, JOI-kun mengubah nilai ketiga menjadi $1$. Jadi, rencana hari pertama adalah $1,2,1$.

Mula-mula, JOI-kun memasok makanan di tempat makanan $1$. Selanjutnya, ia melewati jalan pertama dari tempat makanan $1$ ke tempat makanan $2$ dan memasok makanan di sana. Lalu, ia melewati jalan kedua dari tempat makanan $2$ ke tempat makanan $3$. Terakhir, ia melewati jalan ketiga dari tempat makanan $3$ ke tempat makanan $1$ dan memasok makanan di tempat makanan $1$. Dengan cara ini, rencana dapat dilaksanakan dalam 3 jam. Karena ini waktu minimum, keluarkan 3.

Perhatikan bahwa JOI-kun tidak dapat bergerak melalui tempat makanan $1 \to 2 \to 1$ karena ia tidak dapat berbalik arah.

Masukan 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

Keluaran 2

5
2
3
-1

Penjelasan

Pada contoh 2, rencana hari pertama adalah $4,1,4$. Mula-mula, JOI-kun memasok di tempat makanan $4$. Selanjutnya, ia melewati jalan keempat dari tempat makanan $4$ ke tempat makanan $1$ dan memasok di sana. Lalu, ia melewati jalan pertama, kedua, ketiga, dan keempat secara berurutan, melalui tempat makanan $1 \to 2 \to 3 \to 1 \to 4$, dan memasok di tempat makanan $4$. Cara ini memerlukan waktu minimum.

Rencana hari keempat adalah $2,4,2$. Karena JOI-kun tidak dapat melaksanakan rencana tersebut, keluarkan -1.

Masukan 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

Keluaran 3

38