Mr X is very curious to know about the frequency of stocks. But unfortunately for him, the stocks are represented as nodes of a tree with prices of the stocks as their value. Mr X hates trees as much as he loves to learn about stocks. So he asks for your help:

Given a tree with N nodes (each node represents a stock) numbered from 1 to N (rooted at 1). Each stock has a price/value which is denoted by P_i. He is very curious so he asks a lot of questions of the form: U L R . For each of his question he wants to know how many different stock prices/values are present in the subtree of U for which frequency is between L and R(Both inclusive).

Constraints :

1<=N,Q,U<=10⁵

1<=L<=R<=10⁵

1<=P_i<=10⁵

INPUT:

The first line contains 2 space seperated integers N and Q, the number of nodes in the tree and the number of queries

Following N-1 lines contains 2 integers a and b denoting an edge between a and b

Next line contains N space seperated integers denoting the value of each node

Following Q lines contains 3 space seperated integers U,L,R

OUTPUT:

Output Q lines containing the answer of each query.

Hint :

Sack DSU on tree