音无彩名给你一个数组 $A$，以及一棵 $n$ 个节点的树，每个点有一个颜色，颜色为 $1$ 到 $x$ 的整数。

有 $m$ 次查询，每次查询树上只保留 $[l,r]$ 内的所有节点，设一个极大连通块中出现奇数次数的颜色个数为 $t$，则其对答案的贡献为 $A_t$ ，即答案是所有连通块贡献的和，询问间互相独立。

输入格式

第一行三个用空格隔开的数 $n,m,x$。

第二行 $n$ 个数表示每个点的颜色。

之后 $n-1$ 行每行两个用空格隔开的数 $x,y$ 表示一条边。

之后一行 $x+1$ 个数表示 $A_0$ 到 $A_x$ 。

之后 $m$ 行，每行两个用空格隔开的数 $l,r$ 表示一次询问。

输出格式

输出 $m$ 行，每行一个数表示这次询问的答案。

样例数据

样例输入

6 3 5
1 1 4 5 1 4
1 2
2 3
3 4
4 5
5 6
1 1 4 5 1 4
1 1
4 5
1 4

样例输出

1
4
4

子任务

Idea：nzhtl1477，Solution：nzhtl1477，Code：nzhtl1477，Data：nzhtl1477

注意：本题采用捆绑测试，只有当你通过一个 subtask 中的所有测试点后，你才能拿到这个 subtask 的分数。

对于其中 $1\%$ 的数据，为样例 1。

对于另外 $9\%$ 的数据，$n,m\leq 200$。

对于另外 $19\%$ 的数据，$n,m\leq 2000$。

对于另外 $19\%$ 的数据，$x\leq 10$。

对于 $100\%$ 的数据，$1\leq n,m\leq 10^5$，$1\leq x,A_i \leq 10^4$。