给定一个 $n$ 个点的有根树。

给定 $m$ 组询问，每次给定 $l,r,x$，你需要求出有多少个点 $u$ 满足至少存在一个 $v$ 满足 $l\le v\le r$ 且 $v$ 的 $x$ 级祖先为 $u$。

其中 $v$ 的 $x$ 级祖先表示从 $v$ 开始向根移动 $x$ 步到达的点。若 $v$ 到根的路径上边数 $\le x-1$ 则 $v$ 的 $x$ 级祖先不存在。

输入格式

第一行，两个整数，表示 $n,m$。

第二行，$n$ 个整数，第 $i$ 个数表示节点 $i$ 的父节点编号 $fa_i$。若 $fa_i=0$ 则 $i$ 为根。

接下来 $m$ 行，每行三个整数，表示 $l,r,x$。

输出格式

$m$ 行，每行一个整数，依次表示每组询问的答案。

样例数据

input

7 5
3 1 0 5 3 5 1
1 3 1
5 7 2
1 5 1
4 7 1
4 7 2

output

2
1
3
3
1

子任务

对于 $100\%$ 的数据，$1\le n\le 10^5,1\le m\le 10^6,1\le l\le r\le n,1\le x\le n, 0 \leq fa_i \leq n$。保证 fa 数组构成一棵树。

$\operatorname{Subtask} 1(11\%):n,m\le 10^3$。

$\operatorname{Subtask} 2(13\%):n,m\le 10^4$。

$\operatorname{Subtask} 3(17\%):n\le 5\times 10^4,m\le 2\times 10^5$。

$\operatorname{Subtask} 4(19\%):n\le 10^5,m\le 4\times 10^5$。

$\operatorname{Subtask} 5(17\%):l=1$。

$\operatorname{Subtask} 6(23\%):$ 无特殊限制。