לפי תחזית הסייסמולוגים, צפויה רעידת אדמה חזקה ב־Bitland. ב־Bitland יש $n$ ערים, הממוספרות מ־$1$ עד $n$. חלקן מחוברות בכבישים דו־כיווניים. מסלול הוא סדרת ערים שבה כל שתי ערים עוקבות מחוברות בכביש כלשהו. אורך המסלול הוא סכום אורכי כל הכבישים הכלולים בו. מסלול מינימלי בין זוג ערים $(a,b)$ מוגדר כמסלול בעל האורך המינימלי המתחיל בעיר $a$ ומסתיים בעיר $b$.

ממשלת המדינה רואה בדליפת קרינה מתחנות כוח גרעיניות את הבעיה העיקרית — במקרה כזה יהיה צורך לפנות את האוכלוסייה. כל תחנת כוח גרעינית נמצאת באחת הערים, ומספרן הכולל הוא $k$; בכל עיר יש לכל היותר תחנת כוח גרעינית אחת. הממשלה רוצה להכין תוכנית פינוי שתפעל בזמן רעידת האדמה.

יש לבחור את מסלול הפינוי בין ערים כך שיעבור רחוק ככל האפשר מכל הערים שיש בהן תחנות כוח גרעיניות. מידת המסוכנות של מסלול מחושבת כמרחק המינימלי בין הערים שעל המסלול לבין עיר כלשהי שיש בה תחנת כוח גרעינית. באופן פורמלי יותר, נניח ש־$(a_1,a_2,\ldots,a_s)$ הן הערים שעל המסלול וש־$(g_1,g_2,\ldots,g_k)$ הן הערים שיש בהן תחנות כוח גרעיניות. אז מידת המסוכנות של המסלול שווה למינימום מבין כל הערכים $dist(a_i,g_j)$, כאשר $dist(a,b)$ הוא אורך המסלול המינימלי בין $a$ ל־$b$.

נתונים $Q$ זוגות ערים $(s_i,t_i)$, ולכל אחד מהם עליכם למצוא תוכנית פינוי בעלת מידת מסוכנות מקסימלית.

קלט

השורה הראשונה מכילה שני מספרים שלמים $n$ ו־$m$, המופרדים ברווח ($2\le n\le10^5$, $1\le m\le5\cdot10^5$) — מספר הערים ומספר הכבישים ב־Bitland. לאחר מכן מופיעים ב־$m$ שורות תיאורי הכבישים, כביש אחד בכל שורה. כל כביש נתון באמצעות שלושה מספרים $a_i,b_i,w_i$ ($1\le a_i,b_i\le n$, $1\le w_i\le1000$, $a_i\ne b_i$) — זוג הערים המחוברות ואורך הכביש. השורה הבאה מכילה מספר שלם אחד $k$ ($1\le k\le n$) — מספר הערים שיש בהן תחנות כוח גרעיניות. בשורה הבאה נתונים $k$ מספרים שלמים $g_i$ ($1\le g_i\le n$, לכל $1\le i\le k$) — מספרי הערים שבהן נמצאות תחנות הכוח הגרעיניות. השורה הבאה מכילה מספר שלם אחד $Q$ ($1\le Q\le10^5$) — מספר זוגות הערים שעבורם יש להכין תוכנית פינוי. לאחר מכן, בכל אחת מ־$Q$ השורות הבאות נתון זוג הערים ה־$i$, $(s_i,t_i)$ ($1\le s_i,t_i\le n$, $s_i\ne t_i$).

מובטח שאף כביש אינו מחבר עיר לעצמה, שבין כל זוג ערים יש לכל היותר כביש אחד, ושאפשר להגיע מכל עיר לכל עיר אחרת.

פלט

הדפיסו $Q$ שורות.

בשורה ה־$i$ הדפיסו מספר שלם יחיד — מידת המסוכנות המקסימלית עבור זוג הערים $(s_i,t_i)$.

תת־משימות

משימה זו מכילה חמש תת־משימות:

1. $n\le10^3$, $1\le m\le10^3$, $Q\le10^3$. בין כל אחד מ־$Q$ הזוגות $(s_i,t_i)$ קיים כביש ישיר. 10 נקודות.
2. $n\le10^5$, $Q\le10^5$. בין כל אחד מ־$Q$ הזוגות $(s_i,t_i)$ קיים כביש ישיר. 13 נקודות.
3. $n\le15$, $1\le m\le200$, $1\le Q\le200$. 12 נקודות.
4. $Q=1$. 19 נקודות.
5. המגבלות המופיעות בתיאור הבעיה לעיל. 46 נקודות.

דוגמאות

קלט 1

9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5

פלט 1

5
5
0
7
8

הערה