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