There is a country consisting of $N$ cities numbered with integer numbers from $0$ to $N - 1$ with values $A_i \; (0 \leq i \leq N-1)$, and $N-1$ bidirectional roads connecting them, such that we can travel between any two cities using these roads. In other words, these cities and roads form a tree.

Arya is currently on vacation and plans to visit either city $U$ or city $V$. He wants to choose some starting points on the shortest path between $U$ and $V$ (excluding city $U, V$) so that he can visit at least one of the cities, $U$ or $V$, without passing through a city with a value less than $K$. This means he must not stay or pass through a city (including destition city $U$ or city $V$) that has a value less than $K$.

You will be given $Q$ queries. Every query contains three integers denoting two cities $U, V$ and value $K$. Your task is to help him find the count of the possible starting points for each query.

Input format

• The first line contains an integer $N$ denotes the number of cities.
• The second line contains $N$ space-separated integers denoting the values of cities $A_i$.
• The next $N - 1$ line contains $2$ space-separated integers $u$ and $v$ denoting the connection between cities.
• The fourth line contains $Q$ denoting the number of queries.
• Each of the next $Q$ lines contains three space-separated integers $U, V$ and $K$.

Output format

For each query, print the count of possible cities in a new line.

Constraints

$2 \lt N \le 10 ^ 5$
$0 \leq u, v \leq N-1$
$0 \lt Q \le 10 ^ 5$
$0 \leq U, V \le N-1$
$U \neq V$
$0 \lt A_i\ ,\ K \le 10 ^ 9$