За прогнозом сейсмологів, у Bitland очікується сильний землетрус. У Bitland є $n$ міст, пронумерованих від $1$ до $n$. Деякі з них сполучені двосторонніми дорогами. Маршрутом вважатимемо послідовність міст, у якій кожні два сусідні міста сполучені деякою дорогою. Довжина маршруту дорівнює сумі довжин усіх доріг, що входять до нього. Найкоротший маршрут між парою міст $(a,b)$ — це маршрут мінімальної довжини, який починається в місті $a$ і закінчується в місті $b$.

Уряд країни вважає головною проблемою витік радіації з атомних електростанцій (АЕС): у такому разі знадобиться евакуація населення. Кожна АЕС розташована в одному з міст, їхня загальна кількість дорівнює $k$, і в кожному місті є не більше однієї АЕС. Уряд хоче скласти план евакуації, який працюватиме під час землетрусу.

Маршрут евакуації між містами треба обрати так, щоб він проходив якомога далі від усіх міст з АЕС. Небезпечність маршруту оцінюють за мінімальною відстанню між містами цього маршруту та будь-яким містом з АЕС. Формальніше, нехай $(a_1,a_2,\ldots,a_s)$ — міста маршруту, а $(g_1,g_2,\ldots,g_k)$ — міста з АЕС. Тоді небезпечність маршруту дорівнює мінімуму серед усіх значень $dist(a_i,g_j)$, де $dist(a,b)$ дорівнює довжині найкоротшого маршруту між $a$ та $b$.

Дано $Q$ пар міст $(s_i,t_i)$, для кожної з яких потрібно скласти план евакуації з максимальною небезпечністю.

Вхідні дані

Перший рядок містить два цілі числа $n$ і $m$, розділені пробілом ($2\le n\le10^5$, $1\le m\le5\cdot10^5$), — кількість міст і доріг у Bitland. Далі в $m$ рядках наведено описи доріг, по одному в рядку. Кожну дорогу задано трьома числами $a_i,b_i,w_i$ ($1\le a_i,b_i\le n$, $1\le w_i\le1000$, $a_i\ne b_i$) — парою сполучених міст і довжиною дороги. Наступний рядок містить ціле число $k$ ($1\le k\le n$) — кількість міст з АЕС. У наступному рядку задано $k$ цілих чисел $g_i$ ($1\le g_i\le n$ для $1\le i\le k$) — номери міст, у яких розташовані АЕС. Наступний рядок містить ціле число $Q$ ($1\le Q\le10^5$) — кількість пар міст для плану евакуації. Далі в кожному з $Q$ рядків задано $i$-ту пару міст $(s_i,t_i)$ ($1\le s_i,t_i\le n$, $s_i\ne t_i$).

Гарантується, що жодна дорога не сполучає місто із самим собою, між будь-якою парою міст є не більше однієї дороги, а з кожного міста можна дістатися до будь-якого іншого.

Вихідні дані

Виведіть $Q$ рядків.

В $i$-му рядку виведіть одне ціле число — максимальну небезпечність для пари міст $(s_i,t_i)$.

Підзадачі

Ця задача містить п'ять підзадач:

1. $n\le10^3$, $1\le m\le10^3$, $Q\le10^3$. Між містами кожної з $Q$ пар $(s_i,t_i)$ є пряма дорога. Оцінюється в 10 балів.
2. $n\le10^5$, $Q\le10^5$. Між містами кожної з $Q$ пар $(s_i,t_i)$ є пряма дорога. Оцінюється в 13 балів.
3. $n\le15$, $1\le m\le200$, $1\le Q\le200$. Оцінюється в 12 балів.
4. $Q=1$. Оцінюється в 19 балів.
5. Обмеження з умови задачі вище. Оцінюється в 46 балів.

Приклади

Вхідні дані 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

Вихідні дані 1

5
5
0
7
8

Примітка