Shortest Paths to Multiple Targets

On a directed graph with non-negative weights, find the shortest paths from source to multiple targets; unreachable targets are -1.

See "Input" for the standard input/output conventions and constraints added by this site.

输入格式

n≤200000, m≤300000, w≤10^9; nodes are 1-based, and the input is n m source q, then the edges, then the targets.

输出格式

Output the target distances in order.

样例 1

输入：

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

输出：

3 4 4

样例 2

输入：

4 1 1 2
1 2 5
2 3

输出：

5 -1

样例 3

输入：

3 2 2 2
2 1 0
1 3 0
1 3

输出：

0 0