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.

The president has assigned $Q$ tasks to $Q$ people, and each person has to visit a city $V$ from their current city $U$ to complete their work. However, due to the long travel distances, the president allows them to relax at cities having value $K.$ The workers have come to you seeking assistance in determining the maximum number of cities where they can relax. Your task is to help them find the maximum number of cities where they can relax.

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 tasks.
• Each of the next $Q$ lines contains three space-separated integers $U, V$ and $K$.

Output format

For each task, print the maximum number of cities where they can relax 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$