This page is still under construction.

Parts of this page are still being built. What you see may change.

JOI National Festival

Time limit1sMemory limit128 MB

Summary
Given a connected weighted graph with some festival cities, answer queries asking for the largest possible minimum distance-to-festival along any path between two cities.
Level

Hard8 of 10

Topics
Graph, Shortest path, Union-find, Sorting
Solved
No attempts yet

Problem

The country JOI has NN cities connected by MM bidirectional roads. Every city is connected, so you can travel from any city to any other city.

Festivals are currently being held in KK of the cities. QQ people who dislike festivals each want to travel from a start city to a destination city. For a city, its distance to a festival is defined as the length of the shortest path from that city to the nearest festival city.

Each person may choose any travel route. Given a route, let its value be the smallest 'distance to a festival' among the cities on that route. We want to choose a route so that this value is as large as possible. For each person, output the maximum possible value over all routes. The start and destination cities are part of the route.

Input

The first line contains the number of cities NN, the number of roads MM, the number of festival cities KK, and the number of festival-averse people QQ, separated by spaces.

Each of the next MM lines describes a road as its two endpoint cities and its length, separated by spaces. Each length is between 11 and 10001000 inclusive.

Each of the next KK lines contains the number of a festival city, one per line. The festival city numbers are distinct.

Each of the next QQ lines contains a person's start city and destination city, separated by spaces. The start and destination are different.

Output

Print QQ lines. For each person, in input order, print the value they can achieve (the maximum, over all routes, of the minimum 'distance to a festival' among the cities on the route).

Constraints

  • 2≤N≤100 0002 \le N \le 100\,000
  • 1≤M≤200 0001 \le M \le 200\,000
  • 1≤K≤N1 \le K \le N
  • 1≤Q≤100 0001 \le Q \le 100\,000

Hint

The figures below show the road networks used in the examples. Figure 1 is the first example and Figure 2 is the second example.

Examples2

  1. Example 1

    Input
    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
    Expected output
    7
5
0

  2. Example 2

    Input
    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
    Expected output
    8
8
11
0
6