Problem Description

On the Ouai continent, there are \( n \) cities, numbered from \( 1 \) to \( n \). All cities are connected by \( n - 1 \) undirected roads, forming a tree structure with \( n \) cities and \( n - 1 \) roads.

Each city's market sells gems, with a total of \( m \) different types of gems, numbered from \( 1 \) to \( m \). The market in city \( i \) sells the \( w_i \)-th type of gem. A type of gem may be sold in multiple cities.

K has a gem collector. This collector can collect up to \( c \) gems in a specific order: \( P_1, P_2, \ldots, P_c \). More specifically, the collector needs to first place the \( P_1 \)-th type of gem, then the \( P_2 \)-th type, and so on. The types \( P_1, P_2, \ldots, P_c \) are distinct.

When K arrives at a city, if the type of gem sold in that city's market matches the type currently needed by the collector, he can buy a gem and place it in the collector. Otherwise, he simply passes through the city without doing anything.

Now, K gives you \( q \) queries, each providing a starting point \( s_i \) and an ending point \( t_i \). He wants to know, if he starts from city \( s_i \) and travels the shortest route to city \( t_i \), how many gems can he collect at most in his collector? (Initially, the collector is empty for each query. The gems at the starting and ending cities can be attempted to be collected.)

Input Format

The first line contains three positive integers \( n, m, c \), representing the number of cities, the number of gem 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 these numbers are distinct.
The third line contains \( n \) positive integers \( w_i \), representing the type of gem sold in 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 next 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 starting and ending points for each query.

Output Format

Output \( q \) lines, each containing a single integer, representing the answer to each query in the order they were given.

Sample Input and Output

Input Sample #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 Sample #1

2
2
2
3
1

Input Sample #2

See the attached file gem/gem2.in

Output Sample #2

See the attached file gem/gem2.ans

Input Sample #3

See the attached file gem/gem3.in

Output Sample #3

See the attached file gem/gem3.ans

Notes/Hints

[Data Range]

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 \).

Specific restrictions for each test point are as follows:

见题面 Input 部分

见题面 Output 部分