Problem Statement

Ookayama Grand Hotel has $N$ rooms, and every room is occupied by $1$ guest. There are also $M$ corridors connecting rooms, and the $i$-th corridor connects room $u_i$ and room $v_i$ $(i =1,...,M)$.

One day, the $K$ guests staying in rooms $x_1,\cdots,x_K$ are simultaneously infected with the novel coronavirus. Each guest has an incubation period of $s_j (j = 1,...,N)$ days.

1. If a guest was infected $P$ days ago, that guest recovers and acquires immunity. Once a guest has acquired immunity, that guest is never infected by the virus again.

2. When $s_j$ days have passed since the guest in room $j$ was infected, that guest infects the guests in the rooms adjacent to room $j$ (rooms connected by a corridor) with the novel coronavirus, unless they have immunity. Note that a guest who has already recovered still infects others.

3. If a guest infected with the virus is infected again before recovering, a quarantine takes place in that room (this includes the case of being infected $2$ or more times on the same day). In this case, the guest leaves the hotel and no longer spreads the virus to adjacent rooms from then on.

Constraints

• $1 \le N \le 10^5$
• $1 \le K \le N$
• $0 \le M \le \min (10^5, N\times (N-1)/2)$
• $1 \le P \le 1000$
• $1 \le u_i,v_i \le N (1 \le i \le M)$
• $u_i \neq v_i (1 \le i \le M)$
• $\{u_i,v_i\} \neq \{u_j,v_j\} (i \neq j)$
• $1 \le s_j \le P (1\le j\le N)$
• $1 \le x_i \le N (1 \le i \le K)$
• $x_i \neq x_j (i \neq j)$
• All inputs are integers.

Input

$N$ $K$ $M$ $P$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$
$s_1$
$s_2$
$\vdots$
$s_N$
$x_1$
$x_2$
$\vdots$
$x_K$

Output

Output the answer.

Sample

6 2 5 2
1 2
2 3
3 4
4 5
5 6
1
1
1
1
1
1
1
5

1

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

0

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

1