A 城是一座新兴城市，城里开设了 n 座工厂，分属 k 家单位（有的单位可能没有工厂），其中第 i 座工厂属于第 c_i 家单位。

目前，A城的城内有 n-1 条道路，每条道路的两端是不同的工厂。如果将工厂视作图的点，道路视作图的边，那么这张图是树。

现在A城决定开通该城的前两条公交线路。目前已经决定了：

\bullet 每条公交线路将连接两座不同的工厂，且两座工厂属于同一单位。

\bullet 每条公交线路在现有道路上行驶，且往返的路线是一致的。

\bullet 一条公交线路不会重复经过同一座工厂，两条线路也不会经过同一座工厂。

我们认为：仅仅将某条公交线路的上行、下行方向互换，得到的是本质相同的线路；将两条公交线路互换，得到的也是本质相同的一组方案。

在公交线路的运行过程中，有可能某座工厂由于临时施工，不适合作为公交线路的首末站。不过两座工厂不会同时临时施工。

现在，A城学生算法竞赛协会悬赏 100 分，请你对于平时和 m 次工厂临时施工的情况，分别求出开通公交线路的方案数。

第一行三个正整数 n, m, k。

第二行 n 个数 c_i 表示工厂所属的单位。

接下来 n - 1 行每行两个数 a_i, b_i, 表示有一条道路连接第 a_i, b_i 座工厂。

接下来 m 行每行一个数 k_i，表示第 i 次是第 q_i 座工厂临时施工。

第一行表示平时情况的方案数。

接下来 m 行分别表示各次询问情况下的方案数。

对于所有数据，m ≤ n ≤ 10^5, c_i ≤ k ≤ n。

|  测试点编号   | n\le |      数据性质      |

| :-----------: | :----: | :----------------: |

|     1,2     |  50  |         无         |

|      3      | 10^3 |       k=1        |

|      4      | 10^4 |       k=1        |

|      5      | 10^4 |   k=1,m\le 10    |

|      6      | 10^3 |       m=1        |

|     7,8     | 10^4 |       m=1        |

|    9,10     | 10^4 |   k=2,m\le 10    |

|    11,12    | 10^5 |       k=2        |

|    13,14    | 10^4 | c_{q_i} 互不相同 |

|    15,16    | 10^5 | c_{q_i} 互不相同 |

| 17,18,19,20 | 10^5 |         无         |