题目描述

有 $n$ 座城镇和 $m$ 条双向道路，路网连通。每条道路为红色或蓝色。

设通过道路前携带 $a$ 单位能量。通过红色道路后，能量变为 $a-1$；通过蓝色道路后，能量变为 $\lfloor a/2\rfloor$，即除以 $2$ 后向下取整。

每次出行都从城镇 $1$ 出发，可自由选择路线。给定 $q$ 个目的地 $t$，请分别求出到达时至少剩余 $1$ 单位能量所需的最小初始能量。初始能量为整数，各次出行相互独立。

输入格式

第一行包含四个整数 $n,m,q,L$，分别表示城镇数、道路数、出行次数和答案上限。

接下来 $m$ 行，每行包含三个整数 $u,v,c$，表示一条连接城镇 $u,v$ 的双向道路。其中，$c=1$ 表示红色道路，$c=2$ 表示蓝色道路。

接下来 $q$ 行，每行包含一个整数 $t$，表示本次出行的目的地。

输出格式

按出行顺序输出 $q$ 行，每行输出所需的最小初始能量；若该值超过 $L$，则输出 Large。

样例输入 1

4 3 3 10
1 2 2
2 3 1
3 4 2
2
3
4

样例输出 1

2
4
6

样例 1 解释

沿 $1\to2\to3\to4$ 行进时，初始能量为 $6$，经过三条道路后依次变为 $3,2,1$。

样例输入 2

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

样例输出 2

2
2
3

样例 2 解释

携带 $3$ 单位能量沿 $1\to2\to4$ 行进，到达城镇 $4$ 时恰好剩余 $1$ 单位能量。

数据范围与子任务

对于所有测试数据，保证$2\le n\le2\times10^5$，$n-1\le m\le2\times10^5$，$1\le q\le2\times10^5$，$1\le L\le10^9$，$1\le u<v\le n$，$2\le t\le n$。路网连通，无自环、重边。

每个子任务内的正式测试全部通过，才获得该子任务的分数。