D. Decision Problem
time limit per test
15 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Dinner time! oToToT is looking for a good restaurant, but he has been overwhelmed by the amount of choice. There are $$$n\ (1 \le n \le 3\cdot 10^5)$$$ restaurants and $$$n$$$ types of dishes in the city. The $$$i$$$-th restaurant serves the $$$a_i$$$-th type of dish. Now, oToToT is curious about a question:

"If he walks from the $$$x$$$-th restaurant to the $$$y$$$-th restaurant, is the $$$k$$$-th dish an appropriate choice?"

Since route planning can be exhausting, oToToT has filtered out some redundant streets to ensure that there are exactly one path between any two restaurants; the streets preserved by oToToT form an undirected tree. oToToT answers the question with the following method:

  1. Initially, the $$$k$$$-th dish is believed appropriate.
  2. oToToT moves from the $$$x$$$-th restaurant to the $$$y$$$-th restaurant.
  3. Whenever oToToT reaches a restaurant (including the $$$x$$$-th and the $$$y$$$-th restaurant) that serves the $$$k$$$-th dish, he simply changes his opinion.
  4. oToToT confirms his answer after he reaches the $$$y$$$-th restaurant. There's an exception: if the $$$k$$$-th dish is not served at any of the restaurants on the path, it cannot be appropriate.

oToToT also wants to know the number of appropriate dishes, but he is too tired to solve the problem by himself. oToToT will list $$$q\ (1 \le q \le 3\cdot 10^5)$$$ pairs of $$$(x_i, y_i)$$$. Help him count the number of appropriate dishes between the $$$x_i$$$-th restaurant and the $$$y_i$$$-th restaurant. You must figure out the answer before the next query arrives.

Input

The first line of the input contains an integer $$$n\ (1 \le n \le 3\cdot 10^5)$$$ — the number of restaurants.

The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n\ (1 \le a_i \le n)$$$ — the dish served at each restaurant.

The following $$$n-1$$$ lines of the input contains $$$2$$$ integers $$$u_i$$$ and $$$v_i\ (1 \le u_i, v_i \le n)$$$ — indicating a street between the $$$u_i$$$-th restaurant and the $$$v_i$$$-th restaurant. It is guaranteed that the given streets form a tree.

The next line of the input contains an integer $$$q\ (1 \le q \le 3\cdot 10^5)$$$ — the number of queries.

The following $$$q$$$ lines of the input contains $$$2$$$ integers $$$x^\prime_i$$$ and $$$y^\prime_i\ (1 \le x^\prime_i, y^\prime_i \le n)$$$.

If the last answer is $$$t$$$, then: $$$$$$ \begin{array}{c} x_i = ((x^\prime_i + t) \mod n) + 1 \\ y_i = ((y^\prime_i + t) \mod n) + 1 \end{array} $$$$$$

where $$$\text{mod}$$$ is the modulo operator (e.g. $$$11 \mod 4 = 3$$$). Especially, $$$t$$$ is defined $$$0$$$ before the first query.

Output

For each query, output a integer representing the answer.

Examples
Input
6
1 1 5 5 3 3
1 2
6 2
5 6
4 6
3 5
4
6 1
3 1
3 2
2 4
Output
1
0
2
2
Input
5
1 1 2 2 2
1 2
2 3
3 4
4 5
15
5 5
5 1
4 1
4 2
3 2
5 5
1 2
1 3
5 3
2 2
2 3
1 3
3 3
3 4
3 3
Output
0
1
1
2
1
0
0
1
0
0
1
0
0
1
0
Note

Decoded queries of Sample Input 2 

15
1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5