AT_dwacon6th_final_b Harvest Festival

在某个国家，每年都会在超市举办收集各个城镇收获的农作物的收获节。 这个国家有 $N$ 个城镇，编号为 $0,\ \ldots,\ N-1$。另外，有 $M$ 条道路，编号为 $0,\ \ldots,\ M-1$，第 $i$ 条道路连接城镇 $x_i$ 和城镇 $y_i$，长度为 $d_i$，且是双向的。在所有城镇中，编号为 $a_0,\ \ldots,\ a_{K-1}$ 的 $K$ 个城镇设有超市。 每年举办收获节的超市集合由以下条件决定： - 参展的城镇必须从所有城镇中各选出至少一个。 - 为了保证农作物的新鲜，举办收获节的超市必须是从所有被选中的城镇出发的最短距离不超过 $D$ 的超市。 - 为了尽可能多地举办收获节，满足上述条件的所有超市都要举办收获节。 对于所有超市的集合 $A'\ \subseteq\ \{\ a_0,\ \ldots,\ a_{K-1}\ \}$，计算在 $A'$ 举办收获节的城镇选择方式的个数对 $998244353$ 取余，并将这些结果进行异或（XOR）后输出。

输入按以下格式从标准输入读入。 > $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 \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$ - 输入中的所有值均为整数 - 以城镇为顶点、道路为边构成的无向图中，不含重边和自环 ### 样例说明 1 - 在以下情况下，城镇 $0$ 的超市会举办收获节。 - 仅城镇 $0$ 参展时 - 在以下情况下，城镇 $1$、$2$ 的超市会举办收获节。 - 仅城镇 $1$ 参展时 - 仅城镇 $2$ 参展时 - 城镇 $1$ 和 $2$ 一起参展时 - 在以下情况下，无法举办收获节。 - 城镇 $0$ 和 $1$ 参展时 - 城镇 $0$ 和 $2$ 参展时 - 城镇 $0$、$1$、$2$ 一起参展时 因此，$1\ \mathop{XOR}\ 3\ \mathop{XOR}\ 3 = 1$，输出 $1$。 由 ChatGPT 4.1 翻译