وفقًا لتوقعات علماء الزلازل، يُتوقع حدوث زلزال قوي في Bitland. توجد في Bitland مدن عددها $n$، مرقمة من $1$ إلى $n$. تربط طرق ثنائية الاتجاه بعض هذه المدن. نعرّف المسار بأنه تسلسل من المدن بحيث تصل طريق بين كل مدينتين متتاليتين فيه. طول المسار هو مجموع أطوال جميع الطرق التي يتضمنها. ويُعرّف أقصر مسار بين زوج المدن $(a,b)$ بأنه المسار ذو الطول الأدنى الذي يبدأ في المدينة $a$ وينتهي في المدينة $b$.

تعتبر حكومة البلاد أن تسرب الإشعاع من محطات الطاقة النووية (NPP) هو المشكلة الرئيسية؛ ففي هذه الحالة سيكون إجلاء السكان ضروريًا. تقع كل محطة في إحدى المدن، ويبلغ عدد المحطات الإجمالي $k$، ولا توجد أكثر من محطة واحدة في أي مدينة. تريد الحكومة وضع خطة إجلاء تصلح للعمل أثناء الزلزال.

يجب اختيار مسار الإجلاء بين المدن بحيث يكون بعيدًا قدر الإمكان عن جميع المدن التي تضم محطات نووية. تُقدّر «خطورة» المسار بحساب أدنى مسافة بين المدن الواقعة عليه وأي مدينة تضم محطة نووية. وبصورة أدق، لتكن $(a_1,a_2,\ldots,a_s)$ مدن المسار، ولتكن $(g_1,g_2,\ldots,g_k)$ المدن التي تضم محطات نووية. عندئذ تساوي خطورة المسار أصغر قيمة من جميع القيم $\operatorname{dist}(a_i,g_j)$، حيث تساوي $\operatorname{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$)، وهو عدد أزواج المدن في خطة الإجلاء. ثم يرد الزوج رقم $i$، $(s_i,t_i)$ ($1\le s_i,t_i\le n$، $s_i\ne t_i$)، في كل سطر من الأسطر $Q$ التالية.

من المضمون أنه لا توجد طريق تصل مدينة بنفسها، ولا توجد أكثر من طريق واحدة بين أي زوج من المدن، ويمكن الوصول من أي مدينة إلى أي مدينة أخرى.

الإخراج

اطبع $Q$ أسطر.

في السطر رقم $i$، اطبع عددًا صحيحًا واحدًا: أكبر خطورة ممكنة لزوج المدن $(s_i,t_i)$.

المهام الفرعية

تحتوي هذه المسألة على خمس مهام فرعية:

1. $n\le10^3$، $1\le m\le10^3$، $Q\le10^3$. توجد طريق مباشرة بين مدينتي كل زوج $(s_i,t_i)$ من الأزواج $Q$. قيمتها 10 نقاط.
2. $n\le10^5$، $Q\le10^5$. توجد طريق مباشرة بين مدينتي كل زوج $(s_i,t_i)$ من الأزواج $Q$. قيمتها 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

ملاحظة