小L的空投
题号：NC311993
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}小 L 的科研毫无进展，于是他开始玩一款攻防游戏。
\hspace{15pt}A国的防水河堤被敌国炸毁，河水淹没了主城。
\hspace{15pt}水位在逐日上升，城市也开始被淹没。
\hspace{15pt}A国有 n 个城市，m 条双向通行的公路连接这些城市，第 i 条公路双向连接 u_i,v_i 两个城市，不保证所有城市连通，可能有多条公路连接同一对城市。
\hspace{15pt}每个城市有一个高度 h。在第 i \left(1 \le i \le x\right) 天的时候，水位会上升到 H_i，所有高度小于等于 H_i 的城市都会被淹没，所有与它们直接相连的公路均变为不可通行状态。
\hspace{15pt}为了保证人们的利益，对于每个城市数量大于等于 d 的未被淹没的连通城市集群，都会发放一个空投。
\hspace{15pt}请问每一天总共需要发放多少个空投？

【名词解释】
\hspace{15pt}连通城市集群：即连通块，也称连通分量，满足，
\hspace{23pt}\bullet\,是原图的一个子图；
\hspace{23pt}\bullet\,连通城市集群内的任意两个城市之间都存在路径相连，且路径上的城市也在连通城市集群内；
\hspace{23pt}\bullet\,是极大的，即不能再通过添加原图中的其他城市而依旧保持连通性；
\hspace{15pt}单独的城市也构成一个连通城市集群。

输入描述:

\hspace{15pt}第一行输入四个正整数 n,m,x,d\left(1\le n,m,x\le 5\times 10^5;\, 1\le d \le n\right)，表示城市数、公路数、天数、发放空投的连通城市集群大小。
\hspace{15pt}接下来输入 n 个整数，第 i 个整数 h_i\left(1\le h_i \le 10^9\right)，表示第 i 个城市的高度。
\hspace{15pt}接下来 m 行，每行输入两个正整数 u_i,v_i\left(1\le u_i,v_i\le n;\, u_i \neq v_i\right)，表示第 i 条公路连接的两座城市。
\hspace{15pt}接下来 x 行，每行输入一个正整数 H_i\left(1\le H_i \le 10^9\right)，表示第 i 天水位将上升到 H_i，保证 H_i 严格单调递增。

输出描述:

\hspace{15pt}对于每一天，新起一行输出一个整数，表示当天需要发放的空投数量。
示例1

输入

复制 
5 5 2 2
10 5 8 3 12
1 2
2 3
3 4
4 5
1 5
4
7

输出

复制 
1
1

说明


示例2

输入

复制 
4 3 3 2
5 5 5 5
1 2
2 3
3 4
4
5
6

输出

复制 
1
0
0