Theo dự báo của các nhà địa chấn học, một trận động đất mạnh sắp xảy ra ở Bitland. Bitland có $n$ thành phố, được đánh số từ $1$ đến $n$. Một số thành phố được nối với nhau bằng các con đường hai chiều. Một tuyến đường là một dãy thành phố mà mỗi hai thành phố liên tiếp được nối bằng một con đường. Độ dài của tuyến đường là tổng độ dài của tất cả các con đường được đi qua. Tuyến đường ngắn nhất giữa hai thành phố $(a,b)$ là tuyến đường có độ dài nhỏ nhất bắt đầu tại thành phố $a$ và kết thúc tại thành phố $b$.

Chính phủ coi rò rỉ phóng xạ từ các nhà máy điện hạt nhân (NPP) là vấn đề chính — khi đó cần sơ tán người dân. Mỗi NPP nằm tại một thành phố và tổng cộng có $k$ NPP; mỗi thành phố có không quá một NPP. Chính phủ muốn lập một kế hoạch sơ tán có thể thực hiện trong trận động đất.

Tuyến đường sơ tán giữa các thành phố phải được chọn sao cho cách xa tất cả các thành phố có NPP nhất có thể. Độ nguy hiểm của một tuyến đường được đánh giá bằng khoảng cách nhỏ nhất giữa một thành phố trên tuyến đường và một thành phố bất kỳ có NPP. Chính xác hơn, gọi $(a_1,a_2,\ldots,a_s)$ là các thành phố trên tuyến đường và $(g_1,g_2,\ldots,g_k)$ là các thành phố có NPP. Độ nguy hiểm của tuyến đường là giá trị nhỏ nhất trong tất cả các giá trị $\operatorname{dist}(a_i,g_j)$, trong đó $\operatorname{dist}(a,b)$ là độ dài tuyến đường ngắn nhất giữa $a$ và $b$.

Cho $Q$ cặp thành phố $(s_i,t_i)$. Với mỗi cặp, hãy lập kế hoạch sơ tán có độ nguy hiểm lớn nhất.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $m$, cách nhau bởi dấu cách ($2\le n\le 10^5$, $1\le m\le 5\cdot 10^5$) — số thành phố và số con đường ở Bitland. Tiếp theo là $m$ dòng mô tả các con đường, mỗi dòng một con đường. Mỗi con đường được cho bởi ba số $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$) — hai thành phố được nối và độ dài con đường. Dòng tiếp theo chứa một số nguyên $k$ ($1\le k\le n$) — số thành phố có NPP. Dòng tiếp theo chứa $k$ số nguyên $g_i$ ($1\le g_i\le n$, với $1\le i\le k$) — số hiệu các thành phố có NPP. Dòng tiếp theo chứa một số nguyên $Q$ ($1\le Q\le 10^5$) — số cặp thành phố cần lập kế hoạch sơ tán. Mỗi dòng trong $Q$ dòng tiếp theo chứa cặp thành phố thứ $i$, $(s_i,t_i)$ ($1\le s_i,t_i\le n$, $s_i\ne t_i$).

Đảm bảo rằng không có con đường nào nối một thành phố với chính nó, giữa hai thành phố bất kỳ có không quá một con đường, và có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác.

Dữ liệu ra

In ra $Q$ dòng.

Trên dòng thứ $i$, in một số nguyên — độ nguy hiểm lớn nhất cho cặp thành phố $(s_i,t_i)$.

Nhiệm vụ con

Bài toán có năm nhiệm vụ con:

1. $n\le 10^3$, $1\le m\le 10^3$, $Q\le 10^3$. Với mỗi cặp trong $Q$ cặp $(s_i,t_i)$, có một con đường nối trực tiếp hai thành phố. 10 điểm.
2. $n\le 10^5$, $Q\le 10^5$. Với mỗi cặp trong $Q$ cặp $(s_i,t_i)$, có một con đường nối trực tiếp hai thành phố. 13 điểm.
3. $n\le 15$, $1\le m\le 200$, $1\le Q\le 200$. 12 điểm.
4. $Q=1$. 19 điểm.
5. Các giới hạn như trong đề bài ở trên. 46 điểm.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

5
5
0
7
8

Ghi chú