Problem Description

In a certain country, a harvest festival is held annually at supermarkets, where crops from each town are gathered.

This country has $ N $ towns numbered $0, \ldots, N-1$. There are also $ M $ roads numbered $0, \ldots, M-1$, where road $ i $ connects town $ x_i $ and town $ y_i $ bidirectionally with a length of $ d_i $. Among all towns, supermarkets are located in $ K $ towns numbered $a_0, \ldots, a_{K-1}$.

The set of supermarkets hosting the harvest festival that year is determined by the following conditions:

• At least one town from all towns is selected to exhibit at the festival.
• To hold the festival while the crops are fresh, it is held at supermarkets within a shortest distance of $ D $ from all selected towns.
• As many supermarkets as possible are chosen to host the festival, so all eligible supermarkets host it.

For all subsets $A' \subseteq \{ a_0, \ldots, a_{K-1} \}$ of supermarkets, calculate the number of ways towns can be selected such that the harvest festival is held at $ A' $, modulo $ 998244353 $, and output the XOR of these counts.

Input Format

The input is given from the standard input in the following format:

$ 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} $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

3 1 3 1
0 1 2
1 2 1

Sample Output #1

1

Sample Input #2

5 4 3 2
1 2 3
0 1 2
1 2 1
2 3 5
3 4 5

Sample Output #2

17

Sample Input #3

4 2 4 2
0 1 2 3
0 1 1
2 3 1

Sample Output #3

9

Sample Input #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

Sample Output #4

367

Notes/Hints

Constraints

• $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}$ are distinct
• $0 \leq x_i, y_i \leq N-1$
• $1 \leq d_i \leq 10^9$
• All values in the input are integers
• When considering the undirected graph with towns as vertices and roads as edges, the graph does not contain multiple edges or self-loops

见题面 Input 部分

见题面 Output 部分