Marin 是一个好人，所以他将为他的 $N$ 个朋友举办 $Q$ 场聚会，他的朋友们都是算法竞赛选手。在聚会上唯一提供的饮料是 Džumbus —— 一种可乐和生姜汁的混合饮料。

对于他的每一个朋友，Marin 都知道他们需要喝多少分量的 Džumbus 才能放松下来。他还知道在他的朋友中存在 $M$ 对关系，如果某对关系中的两个人都放松下来，他们就会开始交流以前 COCI 比赛的题目解法（因为没有官方题解发布）。

当人 A 与人 B 分享他们的解法时，人 B 可能会决定以同样的方式分享这些解法。此外，已知这 $M$ 对关系构成的结构中，无论交流以何种顺序进行，这些解法都不可能传回到人 A（即关系图无环，是一个森林）。

Marin 为每场聚会准备了不同总量的 Džumbus。在每场聚会中，他会分配饮料，以最大化在该场聚会上至少与另一个人交流过一次解法的人数。

你的任务是确定在 $Q$ 场聚会中，每场聚会最多有多少人会交流解法。

输入格式

第一行包含两个整数 $N$ 和 $M$，含义如题面所述。

第二行包含 $N$ 个空格分隔的整数 $D_i$，表示让 Marin 的朋友们放松所需的 Džumbus 分量，按朋友编号 $1$ 到 $N$ 的顺序给出。

接下来的 $M$ 行，每行包含两个整数 $A_i$ 和 $B_i$（$A_i \neq B_i$），表示题面中提到的一对朋友关系。

下一行包含一个整数 $Q$，表示聚会的次数。

接下来的 $Q$ 行，每行包含一个整数 $S_i$，表示第 $i$ 场聚会中将提供的 Džumbus 总量。

输出格式

输出 $Q$ 行，每行一个整数，表示对应的聚会中会交流解法的最大人数。每场聚会之间是相互独立的。

数据范围

对于所有子任务，满足 $0 \le M < N \le 1000$，$1 \le Q \le 2 \cdot 10^5$，$1 \le D_i \le 10^9$，$1 \le S_i \le 10^9$。

样例

输入样例 1

1 0
1000
1
1000

输出样例 1

0

输入样例 2

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

输出样例 2

0
2
2

输入样例 3

14 13
2 3 4 19 20 21 5 22 6 7 23 8 10 14
1 2
1 3
1 4
2 5
2 6
3 7
3 8
3 9
4 10
8 11
10 13
10 12
12 14
3
45
44
23

输出样例 3

8
7
5

说明

第三个样例的解释：在第一场聚会上（提供 45 单位 Džumbus），Marin 决定让索引为 1, 2, 3, 7, 9, 10, 12 和 13 的朋友放松。他们总共喝了 45 单位的 Džumbus。