题目描述

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

格式

输入格式

第一行，四个正整数 n,m,s,q，分别表示C城的结点数与边数，学校所在的结点编号，以及小A同学们的数量。 接下来 m 行，每行三个正整数 u_i, v_i, l_i，表示 c 城中的一条无向边。 接下来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≤500,1≤m≤500。 对于所有测试点，保证1≤n≤2x10⁵, 1≤m<2x10⁵, 1≤q≤2x10⁵, 1≤u_i,v_i,s,h_i≤n, 1≤l_i≤10⁶。保证给定的图联通。