You are given a tree with $n$ nodes, where each node has a color. There are $m$ query operations.

Each query is given by parameters $l, r, x$. You need to output the number of distinct colors in the connected component containing $x$ when only nodes with indices in the range $[l, r]$ are kept.

Each query operation is independent.

Input

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers representing the color of each node.

The next $n-1$ lines each contain two integers $x$ and $y$, representing an edge between $x$ and $y$.

The next $m$ lines each contain three integers $l, r, x$, representing a query operation.

Output

For each query, output a single integer representing the answer on a new line.

Examples

Input 1

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

Output 1

3
2
2
3

Note

Idea: nzhtl1477, Solution: nzhtl1477, Code: created_equal1, Data: nzhtl1477

For $100\%$ of the data, all colors are in the range $[1, 10^5]$, and it is guaranteed that $l \le x \le r$ for every query.