On the continent of Oa, there are $n$ cities, numbered $1$ to $n$. All cities are connected by $n-1$ undirected roads, forming a tree.

Each city's market sells a gemstone. There are $m$ different types of gemstones, numbered $1$ to $m$. The market in city $i$ sells a gemstone of type $w_i$. A specific type of gemstone may be sold in multiple cities.

God K has a gemstone collector. This collector can collect at most $c$ gemstones in a specific order: $P_1, P_2, \dots, P_c$. More specifically, the collector must first be loaded with a gemstone of type $P_1$, then a gemstone of type $P_2$, then $P_3$, and so on. Note that $P_1, P_2, \dots, P_c$ are all distinct.

When God K arrives at a city, if the type of gemstone sold at that city's market matches the next type required by the collector, he can purchase that gemstone and place it into the collector; otherwise, he simply passes through the city and does nothing.

God K has given you $q$ queries. Each query provides a starting city $s_i$ and an ending city $t_i$. He wants to know the maximum number of gemstones he can collect if he travels from city $s_i$ to city $t_i$ along the shortest path. (In each query, the collector is initially empty. Gemstones at the starting and ending cities can be collected.)

Input

The input is read from standard input.

The first line contains three positive integers $n, m, c$, representing the number of cities, the number of gemstone types, and the capacity of the collector, respectively.

The second line contains $c$ positive integers $P_i$. It is guaranteed that $1 \le P_i \le m$ and all $P_i$ are distinct.

The third line contains $n$ positive integers $w_i$, representing the type of gemstone sold at each city's market.

The next $n-1$ lines each contain two positive integers $u_i, v_i$, representing a road connecting city $u_i$ and city $v_i$.

The $(n+3)$-th line contains a positive integer $q$, representing the number of queries.

The next $q$ lines each contain two positive integers $s_i, t_i$, representing the start and end cities for that query.

Output

Output $q$ lines, each containing a single integer representing the answer to the corresponding query, in the order they appear in the input.

Examples

Input 1

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

Output 1

2
2
2
3
1

Examples 2

See gem/gem2.in and gem/gem2.ans in the contestant directory.

Examples 3

See gem/gem3.in and gem/gem3.ans in the contestant directory.

Constraints

For all test data: $1 \le n, q \le 2 \times 10^5$, $1 \le c \le m \le 5 \times 10^4$, $1 \le w_i \le m$.

The specific constraints for each test case are as follows: