You are given a tree comprising \(n\) nodes numbered from \(1\) to \(n\). You have to answer \(q\) queries each consisting of three numbers – \(r\), \(d_1\) and \(d_2\). 

For each query, print the number of nodes whose depth is between \(d_1\) and \(d_2\) (inclusive) if the tree is rooted at node \(r\). The depth of root node itself is \(0\), the depth of all its children is \(1\) and so on.

Input format

First line: \(n\) (the number of nodes) and \(q\) (the number of queries)

Next \(n-1\) lines: \(u_i\) and \(v_i\)denoting an edge between the nodes \(u_i\) and \(v_i\).The next \(q\) lines consist of three integers \(r\) , \(d_1\) and \(d_2\) .

Output format

For each query, print the answer in a new line.

input Constraints

\(1 \le n \le 100000\\1 \le q \le 150000\\ 0 \le d_1 \le d_2 \le n\\1 \le r \le n\)