You are very curious to know about the frequency of stocks. The stocks are represented as nodes of a tree with prices of the stocks as their value. 

You are given a tree with $N$ nodes (each node represents a stock) numbered from $1$ to $N$ (rooted at $1$). Each stock has a value that is denoted by $P_i$. You are given queries of the form $U\ L\ R$. For each of the queries, you are required to determine the number of different stock prices or values that are available in the subtree of $U$ for which frequency is between $L$ and $R$ (both inclusive).

Input format

• First line: Two space-separated integers $N$ and $Q$ denoting the number of nodes in the tree and the number of queries respectively
• Next $N-1$ lines: Two integers $a$ and $b$ denoting an edge between $a$ and $b$
• Next line: $N$ space-separated integers denoting the value of each node
• Next $Q$ lines: Three space-separated integers $U$, $L$, and $R$

Output format

Print $Q$ lines containing the answer to each query.

Constraints

$1\le N,Q,U\le10^5\\ 1\le L\le R\le10^5\\ 1\le P_i \le10^5\\$