该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

C 城可以视为由 n 个结点与 m 条边组成的⽆向图 。这些结点依次以 1 , 2, ... , n 标号 ，边依次以 1 , 2, , m 标号 。第 i 条边（ 1 ≤ i ≤ m）连接编号为 ui 与 vi 的结点 ，长度为 li ⽶ 。 ⼩ A 的学校坐落在 C 城中编号为 s 的结点 。⼩ A 的同学们共有 q 位 ，他们想在保证不迟到的前提下 ，每天尽可能晚 地出门上学 。但同学们并不会计算从家需要多久才能到学校 ，于是找到了聪明的⼩ A 。第 i 位同学（ 1 ≤ i ≤ q）告诉⼩ A ，他的家位于编号为 hi 的结点 ，并且他每秒能⾏⾛ 1⽶ 。请你帮⼩ A 计算 ，每位同学从家出发需要多少秒才能到达学校呢？

输入格式

• 第一行：n（结点数），m（边数），s（学校结点），q（同学数）
• 接下来 m 行：每行 u_i, v_i, l_i，表示一条长度为 l_i 的无向边
• 最后 q 行：每行一个 h_i，表示同学家的结点

输出格式

• 共 q 行，每行一个整数，表示从家到学校的最短时间（秒）

样例

输入

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

输出

4
3
1

数据范围

• 20% 数据：q = 1
• 20% 数据：1 ≤ n, m ≤ 500
• 100% 数据：1 ≤ n, q ≤ 2×10⁵，1 ≤ l_i ≤ 10⁶，图保证连通