Según las previsiones de los sismólogos, se espera un fuerte terremoto en Bitland. En Bitland hay $n$ ciudades, numeradas de $1$ a $n$. Algunas están conectadas por carreteras de doble sentido. Una ruta es una secuencia de ciudades en la que cada par de ciudades consecutivas está conectado por alguna carretera. La longitud de una ruta es la suma de las longitudes de todas las carreteras que la componen. Una ruta mínima entre un par de ciudades $(a,b)$ es una ruta de longitud mínima que comienza en la ciudad $a$ y termina en la ciudad $b$.

El gobierno del país considera que el principal problema son las fugas de radiación de las centrales nucleares (NPP): en ese caso será necesario evacuar a la población. Cada central nuclear se encuentra en una ciudad y hay $k$ centrales en total; ninguna ciudad tiene más de una central nuclear. El gobierno quiere elaborar un plan de evacuación que funcione durante el terremoto.

La ruta de evacuación entre ciudades debe elegirse de manera que esté lo más lejos posible de todas las ciudades con centrales nucleares. La peligrosidad de una ruta se calcula como la distancia mínima entre las ciudades de la ruta y cualquier ciudad con una central nuclear. Más formalmente, sean $(a_1,a_2,\ldots,a_s)$ las ciudades de la ruta y $(g_1,g_2,\ldots,g_k)$ las ciudades con centrales nucleares. Entonces, la peligrosidad de la ruta es el mínimo de todos los valores $\operatorname{dist}(a_i,g_j)$, donde $\operatorname{dist}(a,b)$ es la longitud de una ruta mínima entre $a$ y $b$.

Se dan $Q$ pares de ciudades $(s_i,t_i)$; para cada uno debes encontrar un plan de evacuación con la máxima peligrosidad.

Entrada

La primera línea contiene dos enteros $n$ y $m$ separados por un espacio ($2\le n\le10^5$, $1\le m\le5\cdot10^5$): el número de ciudades y el número de carreteras de Bitland. Las siguientes $m$ líneas describen las carreteras, una por línea. Cada carretera se describe mediante tres números $a_i,b_i,w_i$ ($1\le a_i,b_i\le n$, $1\le w_i\le1000$, $a_i\ne b_i$): las ciudades que conecta y su longitud. La siguiente línea contiene un entero $k$ ($1\le k\le n$): el número de ciudades con centrales nucleares. La siguiente línea contiene $k$ enteros $g_i$ ($1\le g_i\le n$ para $1\le i\le k$): los números de las ciudades donde se encuentran las centrales nucleares. La siguiente línea contiene un entero $Q$ ($1\le Q\le10^5$): el número de pares de ciudades del plan de evacuación. A continuación, cada una de las siguientes $Q$ líneas contiene el $i$-ésimo par de ciudades $(s_i,t_i)$ ($1\le s_i,t_i\le n$, $s_i\ne t_i$).

Se garantiza que ninguna carretera conecta una ciudad consigo misma, que entre cualquier par de ciudades hay como máximo una carretera y que es posible llegar de cualquier ciudad a cualquier otra.

Salida

Imprime $Q$ líneas.

En la $i$-ésima línea, imprime un único entero: la máxima peligrosidad para el par de ciudades $(s_i,t_i)$.

Subtareas

Esta tarea contiene cinco subtareas:

1. $n\le10^3$, $1\le m\le10^3$, $Q\le10^3$. Para cada uno de los $Q$ pares $(s_i,t_i)$ existe una carretera directa. Vale 10 puntos.
2. $n\le10^5$, $Q\le10^5$. Para cada uno de los $Q$ pares $(s_i,t_i)$ existe una carretera directa. Vale 13 puntos.
3. $n\le15$, $1\le m\le200$, $1\le Q\le200$. Vale 12 puntos.
4. $Q=1$. Vale 19 puntos.
5. Las restricciones del enunciado anterior. Vale 46 puntos.

Ejemplos

Entrada 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

Salida 1

5
5
0
7
8

Nota