AT_dwacon6th_final_b Harvest Festival

[problemUrl]: https://atcoder.jp/contests/dwacon6th-final/tasks/dwacon6th_final_b とある国では毎年、それぞれの町で採れた作物を集めた収穫祭をスーパーマーケットで開催しています。 この国には $ 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を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ - 入力中の値はすべて整数 - 町を頂点、道を辺とする無向グラフを考えたとき、そのグラフは多重辺や自己ループを含まない ### Sample Explanation 1 \- 以下の場合、町 $ 0 $ のスーパーマーケットで収穫祭が開催されます。 - 町 $ 0 $ が出品する場合 - 以下の場合、町 $ 1 $, $ 2 $ のスーパーマーケットで収穫祭が開催されます。 - 町 $ 1 $ が出品する場合 - 町 $ 1 $, $ 2 $ が出品する場合 - 町 $ 2 $ が出品する場合 - 以下の場合、収穫祭を開催できるスーパーマーケットはありません。 - 町 $ 0 $, $ 1 $ が出品する場合 - 町 $ 0 $, $ 2 $ が出品する場合 - 町 $ 0 $, $ 1 $, $ 2 $ が出品する場合 よって、$ 1\ \mathop{XOR}\ 3\ \mathop{XOR}\ 3\ =\ 1 $ が出力されます。