JOI-kun — дикий кабан, який живе в IOI Forest, де є $N$ пунктів годування та $M$ доріг. Пункти годування пронумеровано від $1$ до $N$. $i$-та дорога ($1\le i\le M$) з'єднує пункти годування $A_i$ та $B_i$ в обох напрямках, і JOI-kun витрачає $C_i$ годин, щоб пройти цією дорогою в будь-якому напрямку. З будь-якого пункту годування можна дістатися до будь-якого іншого, скориставшись однією або кількома дорогами.

JOI-kun погано вміє розвертатися. Він не може розвернутися посеред дороги, щоб повернутися до пункту годування, з якого прийшов. Крім того, прибувши до пункту годування певною дорогою, він не може піти цією самою дорогою назад до пункту годування, де щойно був.

Щодня JOI-kun доставляє їжу до пунктів годування відповідно до плану постачання. План постачання на день складається з послідовності $L$ пунктів годування $X_1,X_2,\ldots,X_L$. Він починає постачання в пункті $X_1$, відвідує пункти в цьому порядку та завершує постачання в пункті $X_L$. Дорогою йому дозволено проходити через інші пункти годування. Можливо, він має доставити їжу до одного пункту кілька разів, але для кожного $j$ ($1\le j\le L-1$) виконується $X_j\ne X_{j+1}$. Зауважте, що може існувати план постачання, який він не здатен виконати.

Спочатку JOI-kun визначає початковий план постачання $X_1,X_2,\ldots,X_L$. Уранці $k$-го дня ($1\le k\le T$) він змінює $P_k$-те значення плану постачання на $Q_k$ (тобто $X_{P_k}$ стає рівним $Q_k$), після чого доставляє їжу за новим планом. Гарантується, що після зміни для кожного $j$ ($1\le j\le L-1$) виконується $X_j\ne X_{j+1}$.

Для кожного плану постачання протягом $T$ днів JOI-kun хоче визначити, чи може він його виконати, і, якщо може, знайти найменший можливий час доставки їжі за цим планом.

Завдання

Маючи дані про IOI Forest та плани постачання JOI-kun, напишіть програму, яка для кожного плану постачання протягом $T$ днів визначає, чи можна його виконати, і, якщо можна, знаходить найменший можливий час доставки їжі за цим планом.

Вхідні дані

Прочитайте такі дані зі стандартного вводу.

• Перший рядок містить чотири цілі числа $N$, $M$, $T$ та $L$, розділені пробілами. Це означає, що в IOI Forest є $N$ пунктів годування та $M$ доріг, JOI-kun розглядає плани постачання на $T$ днів, а план постачання є послідовністю довжини $L$.
• $i$-й рядок ($1\le i\le M$) із наступних $M$ рядків містить три цілі числа $A_i$, $B_i$ та $C_i$, розділені пробілами. Це означає, що $i$-та дорога з'єднує пункти годування $A_i$ та $B_i$ в обох напрямках, і JOI-kun витрачає $C_i$ годин на проходження цією дорогою в будь-якому напрямку.
• $j$-й рядок ($1\le j\le L$) із наступних $L$ рядків містить ціле число $X_j$. Це означає, що початковий план постачання має вигляд $X_1,X_2,\ldots,X_L$.
• $k$-й рядок ($1\le k\le T$) із наступних $T$ рядків містить два цілі числа $P_k$ та $Q_k$, розділені пробілом. Це означає, що вранці $k$-го дня JOI-kun змінює $P_k$-те значення плану постачання на $Q_k$.

Вихідні дані

Виведіть $T$ рядків у стандартний вивід. $k$-й рядок ($1\le k\le T$) має містити -1, якщо виконати план постачання на $k$-й день неможливо, або найменший можливий час у годинах для його виконання, якщо це можливо.

Обмеження

Усі вхідні дані задовольняють такі умови.

• $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$).
• З будь-якого пункту годування можна дістатися до будь-якого іншого, скориставшись однією або кількома дорогами.
• $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$).
• Для кожного $j$ ($1\le j\le L-1$) виконується $X_j\ne X_{j+1}$. Також після кожної зміни плану постачання для кожного $j$ ($1\le j\le L-1$) виконується $X_j\ne X_{j+1}$.

Підзадачі

Є 4 підзадачі. Бали та додаткові обмеження для кожної підзадачі наведено нижче:

Підзадача 1 [12 балів]

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

Підзадача 2 [35 балів]

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

Підзадача 3 [15 балів]

• $T=1$.

Підзадача 4 [38 балів]

Додаткових обмежень немає.

Приклади

Вхідні дані 1

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

Вихідні дані 1

3

Примітка

У першому прикладі початковий план постачання — $1,2,3$. Уранці першого дня JOI-kun змінює третє значення цього плану на $1$. Отже, план постачання на перший день — $1,2,1$.

Спочатку JOI-kun доставляє їжу до пункту $1$. Далі він першою дорогою переходить із пункту $1$ до пункту $2$ та доставляє їжу до пункту $2$. Потім він другою дорогою переходить із пункту $2$ до пункту $3$. Нарешті, третьою дорогою він переходить із пункту $3$ до пункту $1$ і доставляє їжу до пункту $1$. Так виконання плану постачання триватиме 3 години. Оскільки це найменший можливий час, виведіть 3.

Зауважте, що JOI-kun не може рухатися пунктами годування $1\to2\to1$, оскільки він не може розвертатися.

Вхідні дані 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

Вихідні дані 2

5
2
3
-1

Примітка

У другому прикладі план постачання на перший день — $4,1,4$. Спочатку JOI-kun доставляє їжу до пункту $4$. Далі четвертою дорогою він переходить із пункту $4$ до пункту $1$ і доставляє їжу до пункту $1$. Потім він послідовно використовує першу, другу, третю та четверту дороги, рухаючись пунктами $1\to2\to3\to1\to4$, і доставляє їжу до пункту $4$. Це потребує найменшого можливого часу.

План постачання на четвертий день — $2,4,2$. Оскільки JOI-kun не може виконати цей план, виведіть -1.

Вхідні дані 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

Вихідні дані 3

38