Według prognoz sejsmologów w Bitland spodziewane jest silne trzęsienie ziemi. W Bitland jest $n$ miast, ponumerowanych od $1$ do $n$. Niektóre z nich są połączone dwukierunkowymi drogami. Trasą nazywamy ciąg miast, w którym każde dwa kolejne miasta są połączone drogą. Długość trasy jest sumą długości wszystkich dróg należących do niej. Najkrótszą trasą między parą miast $(a,b)$ jest trasa o najmniejszej długości, która zaczyna się w mieście $a$ i kończy w mieście $b$.

Rząd kraju uważa wyciek promieniowania z elektrowni jądrowych (NPP) za główny problem — w takim przypadku konieczna będzie ewakuacja ludności. Każda elektrownia znajduje się w jednym z miast, a ich łączna liczba wynosi $k$; w każdym mieście jest co najwyżej jedna elektrownia. Rząd chce opracować plan ewakuacji, który sprawdzi się podczas trzęsienia ziemi.

Trasę ewakuacji między miastami należy wybrać tak, aby przebiegała jak najdalej od wszystkich miast z elektrowniami jądrowymi. Miarę zagrożenia trasy wyznacza się jako najmniejszą odległość między miastem na trasie a dowolnym miastem z elektrownią. Formalnie, niech $(a_1,a_2,\ldots,a_s)$ będą miastami na trasie, a $(g_1,g_2,\ldots,g_k)$ miastami z elektrowniami. Wówczas miara zagrożenia trasy jest minimum spośród wszystkich wartości $dist(a_i,g_j)$, gdzie $dist(a,b)$ jest długością najkrótszej trasy między $a$ i $b$.

Danych jest $Q$ par miast $(s_i,t_i)$. Dla każdej z nich należy opracować plan ewakuacji o maksymalnej mierze zagrożenia.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $n$ i $m$, rozdzielone spacją $(2 \le n \le 10^5, 1 \le m \le 5 \cdot 10^5)$ — liczbę miast i liczbę dróg w Bitland. Następne $m$ wierszy zawiera opisy dróg, po jednej w każdym wierszu. Każdą drogę opisują trzy liczby $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)$ — para połączonych miast i długość drogi. Następny wiersz zawiera jedną liczbę całkowitą $k$ $(1 \le k \le n)$ — liczbę miast z elektrowniami jądrowymi. W kolejnym wierszu znajduje się $k$ liczb całkowitych $g_i$ $(1 \le g_i \le n$ dla $1 \le i \le k)$ — numery miast, w których znajdują się elektrownie. Następny wiersz zawiera jedną liczbę całkowitą $Q$ $(1 \le Q \le 10^5)$ — liczbę par miast planu ewakuacji. Następnie w każdym z kolejnych $Q$ wierszy podana jest $i$-ta para miast $(s_i,t_i)$ $(1 \le s_i,t_i \le n, s_i \ne t_i)$.

Zagwarantowano, że żadna droga nie łączy miasta z nim samym, między dowolną parą miast jest co najwyżej jedna droga, a z każdego miasta można dotrzeć do każdego innego.

Wyjście

Wypisz $Q$ wierszy.

W $i$-tym wierszu wypisz jedną liczbę całkowitą — maksymalną miarę zagrożenia dla pary miast $(s_i,t_i)$.

Podzadania

To zadanie zawiera pięć podzadań:

1. $n \le 10^3, 1 \le m \le 10^3, Q \le 10^3$. Między każdą z $Q$ par $(s_i,t_i)$ istnieje bezpośrednia droga. Warte 10 punktów.
2. $n \le 10^5, Q \le 10^5$. Między każdą z $Q$ par $(s_i,t_i)$ istnieje bezpośrednia droga. Warte 13 punktów.
3. $n \le 15, 1 \le m \le 200, 1 \le Q \le 200$. Warte 12 punktów.
4. $Q=1$. Warte 19 punktów.
5. Ograniczenia podane powyżej w treści zadania. Warte 46 punktów.

Przykład

Wejście 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

Wyjście 1

5
5
0
7
8

Uwagi