JOI National Festival

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

Festivals are currently being held in $K$ of the cities. $Q$ 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.

The first line contains the number of cities $N$, the number of roads $M$, the number of festival cities $K$, and the number of festival-averse people $Q$, separated by spaces.

Each of the next $M$ lines describes a road as its two endpoint cities and its length, separated by spaces. Each length is between $1$ and $1000$ inclusive.

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

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

Print $Q$ 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).

• $2 \le N \le 100,000$
• $1 \le M \le 200,000$
• $1 \le K \le N$
• $1 \le Q \le 100,000$

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