根據地震學家的預測，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$），表示疏散計畫的城市對數。接下來 $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

說明