给定一棵 $n$ 个节点的有根树，定义 $N(w,d)$（$w$ 为树的顶点，$d$ 为非负整数） 为以 $w$ 为根的子树中，到 $w$ 距离不超过 $d$ 的点构成的集合。

共 $m$ 次询问，每次给出 $w,d$ 查询 $\{N(w',d')\mid N(w',d')\subseteq N(w,d)\}$ 的大小。

输入格式

第一行两个数 $n,m$。

第二行 $n-1$ 个数 $f_2,\dots,f_n$ ，其中 $f_i$ 表示编号 $i$ 的结点的父亲。

接下来 $m$ 行，每行两个数 $w,d$ 表示一次询问。

输出格式

输出 $m$ 行，依次表示每次查询的答案。

样例数据

样例 1 输入

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

样例 1 输出

3
1
1
7

子任务

Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078

对于 $100\%$ 的数据，满足 $1\le n,m\le 10^6$，$1\le f_i < i$，$1\le w\le n$，$0\le d\le n-1$。

对于 $25\%$ 的数据，满足 $n,m\le 100$。

对于另外 $25\%$ 的数据，满足 $n,m\le 5000$。

对于另外 $25\%$ 的数据，满足 $n,m\le 2\times 10^5$。

对于另外 $25\%$ 的数据，无特殊限制。