Problem L
Lead The Way

You are navigating a city represented as a directed graph with $N$ nodes and $E$ weighted edges. There is one central landmark located at node $D$. Note that due to the laziness of the city planner, multi-edges and self-loops are allowed.

For various starting locations in the city, you need to determine the best next step to take to reach node $D$ as quickly as possible. The best next step from a node $x$ is defined as the neighbor $v$ such that there exists a shortest path from $x$ to $D$ starting with the edge $(x, v)$.

If there are multiple neighbors $v$ that lie on a shortest path to $D$, you should choose the one with the smallest node index.

Input

The first line contains three integers $N, E,$ and $D$ ($1 \le N, E \le 2 \cdot 10^5, 1 \le D \le N$), representing the number of nodes, the number of directed edges, and the destination node index.

The next $E$ lines each contain three integers $u, v,$ and $w$ ($1 \le u, v \le N, 1 \le w \le 10^9$), representing a directed edge from $u$ to $v$ with weight $w$. There may be multiple edges between the same pair of nodes.

The next line contains an integer $Q$ ($1 \le Q \le 2 \cdot 10^5$), the number of queries.

The final $Q$ lines each contain a single integer $x$ ($1 \le x \le N$), the starting node for the query.

Output

For each query $x$, output the index of the next node $v$ on the shortest path to $D$.

• If $x = D$, output $D$.

• If there is no path from $x$ to $D$, output $-1$.

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

3
3
3

5 4 5
1 2 5
3 4 1
4 5 1
3 5 2
5
1
2
3
4
5

-1
-1
4
5
5