题目描述

哥萨克·乌斯最近来到了一个非常有趣的国家。这个国家有 $n$ 座城市，其中编号为 $1$ 的城市是国家的首都。这些城市之间恰好有 $n-1$ 条道路，第 $i$ 条道路连接城市 $v_i$ 和 $u_i$。并且，已知从任意一座城市都可以只沿这些道路到达任意另一座城市。

每一座城市都是某个地区的中心。一个地区定义为所有满足如下条件的顶点 $v$ 的集合：从首都到 $v$ 的任意路径都经过该地区的中心。注意，一座城市可以属于多个地区。

编号为 $i$ 的城市中恰好有 $a_i$ 名居民，并且所有 $a_i$ 互不相同。

乌斯得知，这个国家的政府有权执行一种“迁居”操作：选择一对城市 $x$ 和 $y$，把城市 $x$ 中的所有居民迁到城市 $y$，同时把城市 $y$ 中的所有居民迁到城市 $x$。我们的哥萨克最多可以请求政府执行 $k$ 次“迁居”。每次“迁居”选择哪一对城市也由乌斯决定。

每天，哥萨克会选择一个数作为他的最爱数字。如果 $x$ 是乌斯的最爱数字，那么他认为一个地区是“好的”，当且仅当可以执行不超过 $k$ 次“迁居”，使得该地区内各城市人口数的中位数等于 $x$。也就是说，如果把该地区内各城市的人口数按升序排列，那么位于中间的元素应该等于 $x$。如果地区内城市数量为偶数，则中间两个元素中靠右的那个（也就是较大的那个）应该等于 $x$。例如，集合 $\{1,10,2,8,4\}$ 的中位数是 $4$，集合 $\{1,2,10,8\}$ 的中位数是 $8$。

哥萨克还会在这个国家停留恰好 $m$ 天。每天早晨，他会告诉你他的最爱数字，而你需要告诉他“好的”地区数量。

输入格式

第一行包含三个整数 $n,k,g$（$1\le n\le 10^5$，$0\le k\le n$，$0\le g\le 11$），分别表示城市数量、最多执行“迁居”的次数以及测试所属的评分块编号。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le 10^9$），其中 $a_i$ 表示城市 $i$ 的人口数。保证所有数互不相同。

接下来 $n-1$ 行，每行包含两个整数 $v_i,u_i$（$1\le v_i,u_i\le n$），表示这两座城市之间有一条道路。

下一行包含一个整数 $m$（$1\le m\le 10^5$），表示哥萨克将在这个有趣的国家居住的天数。

下一行包含 $m$ 个整数 $x_1,x_2,\ldots,x_m$（$1\le x_i\le 10^9$），其中 $x_i$ 表示第 $i$ 天乌斯的最爱数字。

输出格式

输出 $m$ 个整数，分别表示每一天“好的”地区数量。

输入

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

输出

3 4 5 4 3 

数据范围与评分

1. （$5$ 分）$n,m\le 10^3, k=0$。
2. （$12$ 分）$n,m\le 10^5, k=0$。
3. （$5$ 分）$n,m\le 10^3$，城市 $i$ 与城市 $i+1$ 之间有道路（$1\le i\le n-1$）。
4. （$9$ 分）$n,m\le 10^5$，城市 $i$ 与城市 $i+1$ 之间有道路（$1\le i\le n-1$）。
5. （$5$ 分）$n,m\le 10^3, k=n$。
6. （$11$ 分）$n,m\le 10^5, k=n$。
7. （$8$ 分）$n,m\le 10^2$。
8. （$9$ 分）$n,m\le 10^3$。
9. （$11$ 分）$n\le 10^5, m\le 500$。
10. （$25$ 分）$n,m\le 10^5$。