B - Harvest Festival /

Time Limit: 5.252 sec / Memory Limit: 1024 MB

配点 : 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 で割った余りを計算し、それらのXORを出力してください。

制約

  • 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