問題文

大岡山グランドホテルには $N$ 室の部屋があり、すべての部屋に $1$ 人ずつ客が泊まっています。また、部屋と部屋をつなぐ廊下が $M$ 個あり、 $i$ 番目の廊下は部屋 $u_i$ と部屋 $v_i$ をつないでいます $(i =1,...,M)$ 。

ある日、部屋 $x_1,\cdots,x_K$ に泊まっている $K$ 人の客が一斉に新型コロナウイルスに感染しました。それぞれの客には $s_j (j = 1,...,N)$ 日間の潜伏期間があります。

１．感染してから $P$ 日経った客がいると、その客は回復し、免疫を獲得します。免疫を獲得すると、それ以降ウイルスに感染しなくなります。

２．部屋 $j$ の客が感染してから $s_j$ 日経つと、部屋 $j$ の隣の部屋（廊下でつながっている部屋）の客が免疫を持っていなければ新型コロナウイルスに感染させます。すでに回復している客も他人に感染はさせることに注意してください。

３．ウイルスに感染した客が回復する前にもう一度感染すると、その部屋で検疫が行われます(同じ日に $2$ 回以上感染した場合も含めます)。この場合、客はホテルからいなくなり、以降は隣の部屋にウイルスを広めなくなります。

制約

• $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)$
• 入力は全て整数

入力

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

出力

答えを出力してください。

サンプル

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