题目描述

给定一棵 $n$ 个节点的有根树，根为 $1$，边有边权。$q$ 个询问，每次给出 $p,k,x$，询问有多少个 $p$ 的 $k$ 级后代到 $p$ 的距离小于等于 $x$。

输入格式

本题读入量很大，选手最好使用读入优化。

第一行两个正整数 $n,q$。

接下来 $n-1$ 行，每行三个正整数 $x,y,z$，表示 $x,y$ 间有一条边权为 $z$ 的边。

接下来 $q$ 行，每行三个正整数 $p,k,x$。

输出格式

$q$ 行，每行一个数，表示答案。

样例

输入

5 4
1 2 3
1 3 2
2 5 5
3 4 6
1 2 8
1 2 7
1 1 2
1 1 3

输出

2
0
1
2

数据范围

【数据范围】

对于所有数据，$1\le n,q\le 5\times 10^5$，$1\le p\le n$，$0\le k\le n-1$，所有 $z$ 的和、$x$ 均不超过 $10^9$。

详细数据范围如下表：