ตามการพยากรณ์ของนักแผ่นดินไหววิทยา คาดว่าจะเกิดแผ่นดินไหวรุนแรงใน 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 \le 10^5$, $1 \le m \le 5\cdot10^5$) — จำนวนเมืองและจำนวนถนนใน Bitland จากนั้นมีคำอธิบายถนน $m$ บรรทัด บรรทัดละหนึ่งเส้น ถนนแต่ละเส้นระบุด้วยจำนวนสามจำนวน $a_i,b_i,w_i$ ($1 \le a_i,b_i \le n$, $1 \le w_i \le 1000$, $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 \le 10^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 \le 10^3$, $1 \le m \le 10^3$, $Q \le 10^3$ ระหว่างเมืองแต่ละคู่ $(s_i,t_i)$ จากทั้งหมด $Q$ คู่ มีถนนเชื่อมโดยตรง ได้ 10 คะแนน
2. $n \le 10^5$, $Q \le 10^5$ ระหว่างเมืองแต่ละคู่ $(s_i,t_i)$ จากทั้งหมด $Q$ คู่ มีถนนเชื่อมโดยตรง ได้ 13 คะแนน
3. $n \le 15$, $1 \le m \le 200$, $1 \le Q \le 200$ ได้ 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

หมายเหตุ