Description

Otonashi Ayana gives you an array $A$, and a tree with $n$ nodes. Each node has a color, which is an integer from $1$ to $x$.

There are $m$ queries. For each query, only the nodes in $[l,r]$ are kept on the tree. For a maximal connected component, let $t$ be the number of colors that appear an odd number of times in it. Then its contribution to the answer is $A_t$. That is, the answer is the sum of contributions of all connected components. Queries are independent of each other.

Input Format

The first line contains three integers $n, m, x$ separated by spaces.

The second line contains $n$ integers representing the color of each node.

The next $n - 1$ lines each contain two integers $x, y$ separated by spaces, indicating an edge.

Then one line contains $x + 1$ integers representing $A_0$ to $A_x$.

Then $m$ lines follow, each containing two integers $l, r$ separated by spaces, representing one query.

Output Format

Output $m$ lines. Each line contains one integer, the answer to this query.

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

Hint

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477.

Note: This problem uses bundled tests. Only after you pass all test points in a subtask can you get the score for that subtask.

For $1\%$ of the testdata, it is Sample 1.

For another $9\%$ of the testdata, $n, m \leq 200$.

For another $19\%$ of the testdata, $n, m \leq 2000$.

For another $19\%$ of the testdata, $x \leq 10$.

For $100\%$ of the testdata, $1 \leq n, m \leq 10^5$, $1 \leq x, A_i \leq 10^4$.

Translated by ChatGPT 5