JOI 国のお祭り事情(Festivals in JOI Kingdom)

JOI 国にはN 個の街があり，それらの間はM 本の双方向に通行可能な道路で結ばれている．国民は道路を通ってそれらの街を移動する．

JOI 国の国民には，お祭りが好きな人が多く，現在，K 個の街でお祭りが開催されており，非常に賑わっている．一方で，一部の国民はお祭りを騒がしいとして嫌い，お祭りにできるだけ近づきたくないと思っている．

そこで国王は，優秀なプログラマーであるあなたに，そのようなお祭りを嫌う国民のため，ある街からある街に移動するために，お祭りが開催されている街にどれだけ近づかずに移動することができるかを高速に調べることのできるプログラムの作成を依頼した．

課題

道路の情報とお祭りが開催されている街の情報，およびQ 個のクエリ（出発する街S_i と行きたい街T_iの組）が与えられる．各クエリi に対し，街S_i から街T_i へのすべての経路のうち，お祭りまでの距離が最大となる経路の，お祭りまでの距離を求めるプログラムを作成せよ．ただし，ある経路のお祭りまでの距離とは，経路上の街からお祭りが開催されている街までの移動距離の最小値のことである．

制限

2 ≤ N ≤ 100000 (= 10⁵)     JOI 国の街の個数
1 ≤ M ≤ 200000 (= 2 × 10⁵)     JOI 国の道路の本数
1 ≤ K ≤ N     お祭りが開催されている街の個数
1 ≤ Q ≤ 100000 (= 10⁵)     クエリの個数
1 ≤ L_i ≤ 1000     i 番目の道路の長さ

入力

標準入力から以下のデータを読み込め．

• 1 行目には整数N, M, K, Q が空白を区切りとして書かれている．N はJOI 国の街の個数を，M はJOI国の道路の本数を，K はお祭りが開催されている街の個数を，Q はクエリの個数をそれぞれ表す．街には1, 2, ... , N の番号がつけられている．
• 続くM 行は道路の情報を表す．i + 1 行目(1 ≤ i ≤ M) には整数A_i, B_i, L_i (1 ≤ A_i ≤ N, 1 ≤ B_i ≤ N) が空白を区切りとして書かれている．これは，i 番目の道路が街A_i と街B_i を結んでおり，長さがL_i であることを表す．道路の両端が同じ街であることはない．また，任意の2 つの街p, q に対し，p とqを結ぶ道路は2 本以上存在しない．どの街からどの街へもいくつかの道路をたどって行くことができる．
• 続くK 行はお祭りが開催されている街の情報を表す．i + M + 1 行目(1 ≤ i ≤ K) には1 つの整数F_i(1 ≤ F_i ≤ N) が書かれている．これは街F_i でお祭りが開催されていることを表す．F₁, ..., F_K の中に同じ値が2 回以上現れることはない．
• 続くQ 行はクエリを表す．i + M + K + 1 行目(1 ≤ i ≤ Q) には2 つの整数S_i, T_i (1 ≤ S_i ≤ N, 1 ≤ T_i ≤ N, S_i ≠ T_i) が空白を区切りとして書かれている．これはi 番目のクエリの出発する街がS_i であり行きたい街がT_i であることを表す．

出力

標準出力に，全クエリへの答えをQ 行で出力せよ．すなわち，i 行目に，街S_i から街T_i へのすべての経路のうち，お祭りまでの距離が最大となる経路の，お祭りまでの距離を表す整数を出力せよ．

採点基準

採点用データのうち，
配点の10% 分については，Q = 1 を満たす．
配点の20% 分については，N ≤ 5000, Q ≤ 5000 を満たす．
配点の30% 分については，これら2 つの条件の少なくとも一方を満たす．また，これら2 つの条件の両方を満たすような採点用データはない．

入出力例

入力例 1

6 6 2 3
1 2 5
2 3 4
2 4 6
3 5 9
4 5 3
5 6 7
1
6
3 4
5 2
1 4

出力例 1

7
5
0

6 つの街が6 本の道路で結ばれており，お祭りは街1, 6 の2 つの街で開催されている．クエリは以下の3 つである．

• 1 つ目のクエリは街3 から街4 へ行くというものである．街2 を経由する経路ではお祭りまでの距離は5，街5 を経由する経路ではお祭りまでの距離は7 となるため，答えは7 である．
• 2 つ目のクエリは街5 から街2 へ行くというものである．街3 と街4 のどちらを経由しても，街2 でお祭りまでの距離が最小となり，答えは5 である．
• 3 つ目のクエリは街1 から街4 へ行くというものである．街1 はお祭りが開催されている街であるため，答えは0 となる．

図1: 入力例1

入力例 2

12 17 2 5
1 3 6
1 6 7
2 3 8
2 4 4
2 8 11
2 12 2
3 6 3
3 7 8
3 11 2
4 12 2
5 10 3
6 10 5
8 9 6
8 12 7
9 10 6
11 9 10
12 9 5
8
7
2 6
5 2
1 10
8 9
9 4

出力例 2

8
8
11
0
6

図1: 入力例2

---