Nach den Vorhersagen der Seismologen wird in Bitland ein starkes Erdbeben erwartet. In Bitland gibt es $n$ Städte, die von $1$ bis $n$ nummeriert sind. Einige von ihnen sind durch Straßen verbunden, die in beiden Richtungen befahren werden können. Als Route betrachten wir eine Folge von Städten, in der je zwei aufeinanderfolgende Städte durch eine Straße verbunden sind. Die Länge einer Route ist die Summe der Längen aller auf ihr benutzten Straßen. Eine kürzeste Route zwischen einem Städtepaar $(a,b)$ ist eine Route minimaler Länge, die in Stadt $a$ beginnt und in Stadt $b$ endet.

Die Regierung des Landes betrachtet austretende Strahlung aus Kernkraftwerken (KKW) als das Hauptproblem: In diesem Fall muss die Bevölkerung evakuiert werden. Jedes KKW liegt in einer der Städte, und insgesamt gibt es $k$ KKW. In jeder Stadt gibt es höchstens ein KKW. Die Regierung möchte einen Evakuierungsplan erstellen, der während des Erdbebens funktioniert.

Die Evakuierungsroute zwischen Städten muss so gewählt werden, dass sie möglichst weit von allen Städten mit KKW entfernt verläuft. Die Gefährlichkeit einer Route wird durch den kleinsten Abstand zwischen einer Stadt auf dieser Route und einer beliebigen Stadt mit KKW bestimmt. Formal seien $(a_1,a_2,\ldots,a_s)$ die Städte auf der Route und $(g_1,g_2,\ldots,g_k)$ die Städte mit KKW. Dann ist die Gefährlichkeit der Route das Minimum aller Werte $dist(a_i,g_j)$, wobei $dist(a,b)$ die Länge einer kürzesten Route zwischen $a$ und $b$ ist.

Gegeben sind $Q$ Städtepaare $(s_i,t_i)$. Für jedes davon müssen Sie einen Evakuierungsplan mit maximaler Gefährlichkeit finden.

Eingabe

Die erste Zeile enthält zwei durch ein Leerzeichen getrennte ganze Zahlen $n$ und $m$ ($2 \le n \le 10^5$, $1 \le m \le 5\cdot10^5$), die Anzahl der Städte und die Anzahl der Straßen in Bitland. Es folgen $m$ Zeilen mit je einer Straßenbeschreibung. Jede Straße wird durch drei Zahlen $a_i,b_i,w_i$ ($1 \le a_i,b_i \le n$, $1 \le w_i \le 1000$, $a_i \ne b_i$) beschrieben: die beiden verbundenen Städte und die Länge der Straße. Die nächste Zeile enthält eine ganze Zahl $k$ ($1 \le k \le n$), die Anzahl der Städte mit KKW. In der folgenden Zeile stehen $k$ ganze Zahlen $g_i$ ($1 \le g_i \le n$ für $1 \le i \le k$), die Nummern der Städte mit KKW. Die nächste Zeile enthält eine ganze Zahl $Q$ ($1 \le Q \le 10^5$), die Anzahl der Städtepaare für den Evakuierungsplan. In jeder der nächsten $Q$ Zeilen steht das $i$-te Städtepaar $(s_i,t_i)$ ($1 \le s_i,t_i \le n$, $s_i \ne t_i$).

Es ist garantiert, dass keine Straße eine Stadt mit sich selbst verbindet, dass zwischen jedem Städtepaar höchstens eine Straße verläuft und dass jede Stadt von jeder anderen aus erreichbar ist.

Ausgabe

Geben Sie $Q$ Zeilen aus.

Geben Sie in der $i$-ten Zeile eine ganze Zahl aus: die maximale Gefährlichkeit für das Städtepaar $(s_i,t_i)$.

Teilaufgaben

Diese Aufgabe besteht aus fünf Teilaufgaben:

1. $n \le 10^3$, $1 \le m \le 10^3$, $Q \le 10^3$. Zwischen jedem der $Q$ Paare $(s_i,t_i)$ gibt es eine direkte Straße. 10 Punkte.
2. $n \le 10^5$, $Q \le 10^5$. Zwischen jedem der $Q$ Paare $(s_i,t_i)$ gibt es eine direkte Straße. 13 Punkte.
3. $n \le 15$, $1 \le m \le 200$, $1 \le Q \le 200$. 12 Punkte.
4. $Q=1$. 19 Punkte.
5. Es gelten die Beschränkungen aus der obigen Aufgabenstellung. 46 Punkte.

Beispiele

Eingabe 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

Ausgabe 1

5
5
0
7
8

Hinweis