According to the forecast of seismologists a strong earthquake is expected in Bitland. There are $n$ cities in Bitland, numbered from $1$ to $n$. Some of them are connected by two way roads. We consider route as a sequence of cities, where each consequent two cities are connected by some road. Length of the route is the sum of lengths of all roads that are involved in the route. Minimal route between pair of cities $(a,b)$ is defined by the route with minimal length that starts in city $a$ and ends in city $b$.

The country’s government considers radiation leakage from nuclear power plants (NPP) as the main problem — in this case, evacuation of the population will be required. Each NPP is located in one of the cities and their total number is equal to $k$, each city has no more than one NPP. The government wants to draw up an evacuation plan that will work during the earthquake.

The route of evacuation between cities must be chosen, so that it lays as far as possible from all cities with NPP. The dangerousness of the route is estimated by calculating the minimal distance between cities on that route and any city with NPP. More formally, let $(a_1,a_2,\ldots,a_s)$ be cities on the route and let $(g_1,g_2,\ldots,g_k)$ be the cities with NPP, then dangerousness of the route equals to the minimum among all values of $\operatorname{dist}(a_i,g_j)$, where $\operatorname{dist}(a,b)$ is equal to the length of the minimal route between $a$ and $b$.

Given $Q$ pairs of cities $(s_i,t_i)$ for each of which you have to come up with evacuation plan with maximal dangerousness.

Input

The first line contains two integers $n$ and $m$ separated by space ($2\le n\le10^5$, $1\le m\le5\cdot10^5$) — the number of cities and the number of roads in Bitland. Then in $m$ lines there are descriptions of roads, one per line. Each road is given by three numbers $a_i,b_i,w_i$ ($1\le a_i,b_i\le n$, $1\le w_i\le1000$, $a_i\ne b_i$) — pair of connected cities and length of the road. The next line contains one integer $k$ ($1\le k\le n$) — number of cities with NPP. On the next line $k$ integers $g_i$ ($1\le g_i\le n$, for $1\le i\le k$) are given — the numbers of cities in which NPP are located. The next line contains one integer $Q$ ($1\le Q\le10^5$) — the number of pairs of cities of evacuation plan. Then on each of next $Q$ lines $i$-th pair of cities $(s_i,t_i)$ ($1\le s_i,t_i\le n$, $s_i\ne t_i$) are given.

It is guaranteed, that no road connects the city with itself, between any pair of cities there are no more than one road and it is possible to reach any city from any city.

Output

Output $Q$ lines.

On $i$-th line output single integer — maximal dangerousness for the pair of cities $(s_i,t_i)$.

Subtasks

This task contains five sub-tasks:

1. $n\le10^3$, $1\le m\le10^3$, $Q\le10^3$. Between each of $Q$ pairs $(s_i,t_i)$ there exists a direct road, Scored 10 points.
2. $n\le10^5$, $Q\le10^5$. Between each of $Q$ pairs $(s_i,t_i)$ there exists a direct road. Scored 13 points.
3. $n\le15$, $1\le m\le200$, $1\le Q\le200$. Scored 12 points.
4. $Q=1$. Scored 19 points.
5. Constraints from problem statement above. Scored 46 points.

Examples

Input 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

Output 1

5
5
0
7
8

Note