問題文

とある国では毎年、それぞれの町で採れた作物を集めた収穫祭をスーパーマーケットで開催しています。

この国には $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