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$. يُسمح له بالمرور بمحطات أخرى في أثناء ذلك. وقد يُطلب منه تزويد المحطة نفسها عدة مرات، لكن $X_j \ne X_{j+1}$ لكل $j$ ($1 \le j \le L-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$)، ثم يزوّد المحطات وفقًا للخطة الجديدة. من المضمون أن $X_j \ne X_{j+1}$ لكل $j$ ($1 \le j \le L-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$. وهذا يعني أن JOI-kun يغيّر القيمة ذات الترتيب $P_k$ في الخطة إلى $Q_k$ في صباح اليوم رقم $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$).
• $X_j \ne X_{j+1}$ لكل $j$ ($1 \le j \le L-1$). وبعد كل تغيير في الخطة أيضًا، يتحقق $X_j \ne X_{j+1}$ لكل $j$ ($1 \le j \le L-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$ إلى المحطة $3$. وأخيرًا يستخدم الطريق الثالث للانتقال من المحطة $3$ إلى المحطة $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\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