Ayanami Ayana gives you an array $A$ and a tree with $n$ nodes, where each node has a color represented by an integer from $1$ to $x$.

There are $m$ queries. For each query, only nodes with indices in the range $[l, r]$ are kept in the tree. For each maximal connected component, let $t$ be the number of colors that appear an odd number of times within that component. The contribution of this component to the answer is $A_t$. The total answer is the sum of contributions from all such connected components. Queries are independent of each other.

Input

The first line contains three space-separated integers $n, m, x$.

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

The next $n-1$ lines each contain two space-separated integers $x, y$, representing an edge.

The next line contains $x+1$ integers representing $A_0$ to $A_x$.

The next $m$ lines each contain two space-separated integers $l, r$, representing a query.

Output

Output $m$ lines, each containing the answer for the corresponding query.

Examples

Input 1

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

Output 1

1
4
4

Subtasks

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

Note: This problem uses bundled testing. You will only receive points for a subtask if you pass all test cases within that subtask.

For $1\%$ of the data, the input is the sample case.

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

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

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

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