问题描述

某个国家每年在各个城镇的超市举办收获节，收集当地收获的作物。

这个国家有 $N$ 个城镇，分别编号为 $0, \\ldots, N-1$。此外，有 $M$ 条道路，编号为 $0, \\ldots, M-1$，道路 $i$ 在城镇 $x_i$ 和城镇 $y_i$ 之间双向连接，长度为 $d_i$。 在所有城镇中，有 $K$ 个城镇有超市，编号为 $a_0, \\ldots, a_{K-1}$。

超市的选择满足以下条件：

• 所选的城镇必须包括至少一个出品的城镇。
• 为了确保作物新鲜，超市所选城镇的最短距离不能超过 $D$。
• 为了举办尽可能多的超市，所有满足上述条件的超市都会举办收获节。

对于所有超市集合 $A' \\subseteq \\{ a_0, \\ldots, a_{K-1} \\}$，计算可以在 $A'$ 中举办收获节的城镇选择方式数目，并将它们的异或值输出。

约束条件

• $1 \\leq N \\leq 10^5$
• $0 \\leq M \\leq \\min \\left(N(N-1)/2, 2 \\times 10^5 \\right)$
• $1 \\leq K \\leq \\min(N, 20)$
• $1 \\leq D \\leq 10^9$
• $0 \\leq a_i \\leq N-1$
• $a_0, \\ldots, a_{K-1}$ 互不相同
• $0 \\leq x_i, y_i \\leq N-1$
• $1 \\leq d_i \\leq 10^9$
• 输入中所有值均为整数
• 将城镇视为顶点，道路视为边的无向图不包含重边和自环

输入

输入以以下格式从标准输入中给出。

$N$ $M$ $K$ $D$ $a_0$ $a_1$ $\\ldots$ $a_{K-1}$ $x_0$ $y_0$ $d_0$ $\\vdots$ $x_{M-1}$ $y_{M-1}$ $d_{M-1}$

输出

输出答案。

示例1

3 1 3 1
0 1 2
1 2 1

输出示例1

1

• 在以下情况下，收获节将在城镇 $0$ 的超市举办。
  • 城镇 $0$ 出品的情况
• 在以下情况下，收获节将在城镇 $1, 2$ 的超市举办。
  • 城镇 $1$ 出品的情况
  • 城镇 $1, 2$ 出品的情况
  • 城镇 $2$ 出品的情况
• 在以下情况下，没有超市可以举办收获节。
  • 城镇 $0, 1$ 出品的情况
  • 城镇 $0, 2$ 出品的情况
  • 城镇 $0, 1, 2$ 出品的情况

因此，输出为 $1\\ \\mathop{XOR}\\ 3\\ \\mathop{XOR}\\ 3 = 1$。

示例2

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

输出示例2

17

示例3

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

输出示例3

9

示例4

9 9 4 6
1 3 6 8
1 4 4
6 7 1
4 5 3
3 6 2
4 7 5
7 8 1
1 5 3
1 0 2
4 8 1

输出示例4

367