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