Segundo a previsão dos sismólogos, espera-se um forte terremoto em Bitland. Há $n$ cidades em Bitland, numeradas de $1$ a $n$. Algumas delas estão ligadas por estradas de mão dupla. Uma rota é uma sequência de cidades na qual cada par de cidades consecutivas está ligado por uma estrada. O comprimento da rota é a soma dos comprimentos de todas as estradas que ela percorre. A rota mínima entre um par de cidades $(a,b)$ é uma rota de comprimento mínimo que começa na cidade $a$ e termina na cidade $b$.

O governo do país considera o vazamento de radiação das usinas nucleares como o principal problema: nesse caso, será necessário evacuar a população. Cada usina nuclear está localizada em uma das cidades, e há $k$ usinas ao todo, com no máximo uma em cada cidade. O governo quer elaborar um plano de evacuação que funcione durante o terremoto.

A rota de evacuação entre as cidades deve ser escolhida de modo a ficar o mais longe possível de todas as cidades com usinas nucleares. A periculosidade da rota é avaliada calculando a distância mínima entre as cidades dessa rota e qualquer cidade com uma usina nuclear. Mais formalmente, sejam $(a_1,a_2,\ldots,a_s)$ as cidades da rota e $(g_1,g_2,\ldots,g_k)$ as cidades com usinas nucleares. A periculosidade da rota é o mínimo de todos os valores $dist(a_i,g_j)$, onde $dist(a,b)$ é o comprimento da rota mínima entre $a$ e $b$.

São dados $Q$ pares de cidades $(s_i,t_i)$, para cada um dos quais você deve elaborar um plano de evacuação com periculosidade máxima.

Entrada

A primeira linha contém dois inteiros $n,m$ separados por um espaço ($2\le n\le10^5$, $1\le m\le5\cdot10^5$): o número de cidades e o número de estradas em Bitland. As próximas $m$ linhas descrevem as estradas, uma por linha. Cada estrada é dada por três 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$): o par de cidades ligadas e o comprimento da estrada. A linha seguinte contém um inteiro $k$ ($1\le k\le n$): o número de cidades com usinas nucleares. A próxima linha contém $k$ inteiros $g_i$ ($1\le g_i\le n$, para $1\le i\le k$): os números das cidades onde se encontram as usinas nucleares. A linha seguinte contém um inteiro $Q$ ($1\le Q\le10^5$): o número de pares de cidades do plano de evacuação. Em seguida, cada uma das próximas $Q$ linhas contém o $i$-ésimo par de cidades $(s_i,t_i)$ ($1\le s_i,t_i\le n$, $s_i\ne t_i$).

É garantido que nenhuma estrada liga uma cidade a ela mesma, que há no máximo uma estrada entre cada par de cidades e que é possível chegar de qualquer cidade a qualquer outra.

Saída

Imprima $Q$ linhas.

Na $i$-ésima linha, imprima um único inteiro: a periculosidade máxima para o par de cidades $(s_i,t_i)$.

Subtarefas

Esta tarefa contém cinco subtarefas:

1. $n\le10^3$, $1\le m\le10^3$, $Q\le10^3$. Existe uma estrada direta entre as cidades de cada um dos $Q$ pares $(s_i,t_i)$. Vale 10 pontos.
2. $n\le10^5$, $Q\le10^5$. Existe uma estrada direta entre as cidades de cada um dos $Q$ pares $(s_i,t_i)$. Vale 13 pontos.
3. $n\le15$, $1\le m\le200$, $1\le Q\le200$. Vale 12 pontos.
4. $Q=1$. Vale 19 pontos.
5. As restrições do enunciado acima. Vale 46 pontos.

Exemplos

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

Saída 1

5
5
0
7
8

Observação