JOI-kun הוא חזיר בר החי ביער IOI, שבו $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 ותוכניות האספקה של JOI-kun, כתבו תוכנית שעבור כל אחת מתוכניות האספקה של $T$ הימים קובעת אם הוא יכול לבצע אותה, ואם כן, מוצאת את הזמן הקצר ביותר האפשרי לאספקת המזון לפיה.

קלט

קראו את הנתונים הבאים מהקלט הסטנדרטי.

• השורה הראשונה מכילה ארבעה מספרים שלמים $N$, $M$, $T$ ו-$L$, המופרדים ברווחים. פירוש הדבר הוא שביער IOI יש $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$).
• מתקיים $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$. אז הוא יעבור בדרך השנייה מתחנת המזון $2$ לתחנת המזון $3$. לבסוף הוא יעבור בדרך השלישית מתחנת המזון $3$ לתחנת המזון $1$ ויספק מזון בתחנת המזון $1$. בדרך זו ביצוע תוכנית האספקה יארך 3 שעות. מכיוון שזהו הזמן הקצר ביותר האפשרי, יש להדפיס $3$.

שימו לב ש-JOI-kun אינו יכול לעבור בין תחנות המזון במסלול $1 \to 2 \to 1$, מכיוון שאינו יכול לבצע פניית פרסה.

קלט 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 \to 2 \to 3 \to 1 \to 4$, ויספק מזון בתחנת המזון $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