Secure Trade Route

In a post-apocalyptic world, trade routes are crucial for survival but are threatened by a zombie outbreak. The cities are connected by bidirectional roads with positive weights. Some cities have been overrun by zombies, and passing through these cities (except at times when the destination is the same as the source) is forbidden.

You are given a network with:

• \(n\) cities numbered from 1 to \(n\).
• \(m\) roads connecting pairs of cities, each with a travel cost \(w\). Roads are bidirectional.
• A list of \(k\) zombie-infested cities.
• \(q\) queries; each query asks for the minimum cost route between a source and a destination city that does not pass through any zombie-infested city. Note that if the source is a zombie-infested city (and is not the destination) or the destination is zombie-infested, the answer is defined to be -1.

The secure distance between two cities, if a safe path exists, is computed as \(d = \min \sum_{i \in path} w_i\). If no such safe path exists, output -1.

Your task is to compute the answer for each query.

inputFormat

The input is read from standard input (stdin) and has the following format:

 n m k q
 u1 v1 w1
 u2 v2 w2
 ... (m lines in total)
 z1 z2 ... zk
 s1 t1
 s2 t2
 ... (q lines in total)

where:

• n is the number of cities.
• m is the number of roads.
• k is the number of zombie-infested cities.
• q is the number of queries.
• Each road is described by three integers u, v, w indicating there is a road between city u and city v with weight w.
• The next line contains k integers representing the zombie-infested cities.
• Each of the following q lines contains two integers s and t representing a query from source city s to destination city t.

outputFormat

For each query, output the minimum cost of a secure route on a separate line. If no secure route exists, output -1.

## sample

10 13 2 1
1 2 4
1 3 2
2 3 5
2 4 10
3 5 3
4 5 4
5 6 11
4 6 1
3 7 8
7 8 6
4 9 7
7 10 2
5 7 3
10 5
1 6

15