题目背景

卧龙先生喜欢养小鸡。

题目描述

卧龙先生住在 X 国。众所周知，X 国一共有 $n$ 个城镇，这些城镇间有 $m$ 条道路，每条道路连接了两个不同的城镇，并且任意两个城镇都可以通过一些道路相互到达。

由于某些原因，每条道路只有出租车能通行。第 $i(1\leq i\leq m)$ 条道路的出租车可以在城镇 $a_i$ 和城镇 $b_i$ 之间双向移动，其颜色为 $c_i$ ：当 $c_i=1$ 时为红色，$c_i=2$ 时为蓝色。因为天下没有免费的出租车，所以每次乘坐出租车都要付钱。坐出租车时携带的钱的变化如下：

• 设坐车前带了 $a$ 元。
• 出租车为红色时，坐车后带的钱变为 $a-1$ 元。
• 出租车为蓝色时，坐车后带的钱变为 $\left\lfloor\frac{a}{2}\right\rfloor$ 元。

卧龙先生的家在 X 国的 $1$ 号城镇，他有 $Q$ 个朋友，第 $j(1\leq j\leq Q)$ 个朋友住在城镇 $t_j$。卧龙先生想知道：从他的家出发，去到第 $j$ 个朋友家玩，要使他到达朋友的家之后还剩下至少 $1$ 元，那么他在出发时至少要带多少元钱？但是卧龙先生不喜欢太大的数字，所以如果他要带的钱大于 $L$ 元，就使用 Large 代替它。

由于卧龙先生忙于和飞机哥练习太极推手，所以他把问题交给了你——凤雏。作为卧龙先生最好的朋友，请帮助他解决这一个问题。

输入格式

第一行四个正整数，分别为 $n,m,Q,L$，分别表示 X 国的城镇数量、道路数量、卧龙先生的朋友数量和他所带的钱数限制。

第 $2\sim m-1$ 行，每行三个正整数 $a_i,b_i,c_i$，表示这条道路连接的两个城镇编号与出租车的颜色。

第 $m+2\sim m+Q+1$ 行，每行一个正整数 $t_j$，表示卧龙先生的第 $j$ 个朋友的家的城镇编号。

输出格式

共 $Q$ 行，每行一个整数或者字符串 Large，表示卧龙先生到第 $j$ 个朋友家至少要带的钱数。

样例 1 输入

7 6 1 10
1 2 2
2 3 1
3 4 2
4 5 1
5 6 1
6 7 2
5

样例 1 输出

10

样例 2 输入

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

样例 2 输出

Large
22
4

样例 3 输入

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

样例 3 输出

4

样例 4 输入

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

样例 4 输出

2
Large
7
5
3

样例 5 ~ 6

见下发文件。

测试点约束

对于所有数据，保证 $2\leq n\leq 2\times 10^5$，$n-1\leq m\leq 2\times 10^5$，$1\leq Q\leq 2\times 10^5$，$1\leq L\leq 10^9$，$1\leq c_i\leq 2$，$2\leq t_j\leq n$，图无重边、自环。

每个子任务的具体约束见下表：

特殊性质 $\mathrm{A}$：$a_i=i,b_i=i+1(1\leq i\leq m)$。

特殊性质 $\mathrm{B}$：$c_i=1(1\leq i\leq m)$。

特殊性质 $\mathrm{C}$：$1\leq L\leq 100$。