配点 : 800 点
問題文
在某个国家,超市每年都会举办丰收节,汇集各个城镇种植的农作物。
在这个国家 有 N 个城镇,每个城镇都有 它的编号为 0, \ldots, N-1 。 另外, 编号为0, \ldots, M-1 它有多个 M 有一条书的路,一条路 i 是一个城镇 x_i 和镇 y_i 是长度 它在两个方向上都与 d_i 连接。 在所有城镇中,数量 a_0, \ldots, a_{K-1} 的 K 城镇有超市。
当年举办丰收节的超市组根据以下条件确定。
- 各城镇将邀请所有城镇在丰收节上展示物品。 1 已选择多于一项
- 为了在农作物新鲜时举办活动,距所有选定城镇的最短距离是 在 D 内的一家超市举行
- 为了在尽可能多的超市举办活动,将在上述所有超市举办。
所有超市合集 A' \subseteq \{ a_0, \ldots, a_{K-1} \} , 当我输入A' 计算选择举办丰收祭的城镇的方法数。 计算除以 998244353 后的余数并输出它们的异或。
制約
- 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