Selon les prévisions des sismologues, un puissant séisme est attendu à Bitland. Bitland compte $n$ villes, numérotées de $1$ à $n$. Certaines sont reliées par des routes à double sens. Un itinéraire est une suite de villes dont deux villes consécutives sont toujours reliées par une route. La longueur de l’itinéraire est la somme des longueurs de toutes les routes qu’il emprunte. Un itinéraire minimal entre deux villes $(a,b)$ est un itinéraire de longueur minimale qui commence dans la ville $a$ et se termine dans la ville $b$.

Le gouvernement considère que le principal problème est le risque de fuite radioactive des centrales nucléaires (CN) : dans ce cas, la population devra être évacuée. Chaque CN est située dans une ville ; il y en a $k$ au total et chaque ville en compte au plus une. Le gouvernement souhaite établir un plan d’évacuation qui fonctionnera pendant le séisme.

L’itinéraire d’évacuation entre deux villes doit être choisi de manière à passer aussi loin que possible de toutes les villes possédant une CN. La dangerosité d’un itinéraire est évaluée en calculant la distance minimale entre une ville de l’itinéraire et une ville possédant une CN. Plus formellement, soient $(a_1,a_2,\ldots,a_s)$ les villes de l’itinéraire et $(g_1,g_2,\ldots,g_k)$ les villes possédant une CN. La dangerosité de l’itinéraire est alors le minimum de toutes les valeurs $dist(a_i,g_j)$, où $dist(a,b)$ est la longueur d’un itinéraire minimal entre $a$ et $b$.

On vous donne $Q$ paires de villes $(s_i,t_i)$. Pour chacune, vous devez établir un plan d’évacuation de dangerosité maximale.

Entrée

La première ligne contient deux entiers $n$ et $m$ séparés par un espace $(2\le n\le10^5,\ 1\le m\le5\cdot10^5)$ : le nombre de villes et le nombre de routes de Bitland. Les $m$ lignes suivantes décrivent les routes, une par ligne. Chaque route est donnée par trois nombres $a_i,b_i,w_i$ $(1\le a_i,b_i\le n,\ 1\le w_i\le1000,\ a_i\ne b_i)$ : les deux villes reliées et la longueur de la route. La ligne suivante contient un entier $k$ $(1\le k\le n)$ : le nombre de villes possédant une CN. La ligne suivante contient $k$ entiers $g_i$ $(1\le g_i\le n,\ 1\le i\le k)$ : les numéros des villes où se trouvent les CN. La ligne suivante contient un entier $Q$ $(1\le Q\le10^5)$ : le nombre de paires de villes du plan d’évacuation. Chacune des $Q$ lignes suivantes donne la $i$-ème paire de villes $(s_i,t_i)$ $(1\le s_i,t_i\le n,\ s_i\ne t_i)$.

Il est garanti qu’aucune route ne relie une ville à elle-même, qu’il existe au plus une route entre deux villes et qu’il est possible de rejoindre n’importe quelle ville depuis n’importe quelle autre.

Sortie

Affichez $Q$ lignes.

Sur la $i$-ème ligne, affichez un seul entier : la dangerosité maximale pour la paire de villes $(s_i,t_i)$.

Sous-tâches

Cette tâche comporte cinq sous-tâches :

1. $n\le10^3,\ 1\le m\le10^3,\ Q\le10^3$. Chacune des $Q$ paires $(s_i,t_i)$ est reliée par une route directe. Vaut 10 points.

2. $n\le10^5,\ Q\le10^5$. Chacune des $Q$ paires $(s_i,t_i)$ est reliée par une route directe. Vaut 13 points.

3. $n\le15,\ 1\le m\le200,\ 1\le Q\le200$. Vaut 12 points.

4. $Q=1$. Vaut 19 points.

5. Les contraintes de l’énoncé ci-dessus. Vaut 46 points.

Exemples

Entrée 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

Sortie 1

5
5
0
7
8

Remarque