题目背景

一位 OIer Cu 后变成了 whker，这是他身体发生的变化。

题目描述

Displace Cu 了，于是他滚回whk。

然而他仍然放不下他在机房种下的树，于是他经常逃课run回机房照看他的树。

因为一些原因，这棵树的根节点是1。

有一天他突然发现笔记本上写下了一个神秘的长度为 $n$ 的排列，长度刚好和他种下的树的节点个数相同。他选取了这个序列的某个区间。他开始思考，如果在树上只保留这个区间的节点（），会是什么样子，很显然大概率是不连通的。

他联想到虚树的相关知识，于是他保留这个区间任意两点的lca，这样通过虚树边就可以连通了。

现在他想知道，这棵虚树有多少个点。

Displace会进行 $m$ 次询问，你需要对每次询问都回答出这个区间的点形成的虚树的节点个数。

形式化题意：给出一棵以1号点为根的树和元素为1到 $n$的排列 $a$，$m$ 次询问一段区间 $l, r$，将 $\forall_{l\leq i<j\leq r} lca(a_i, a_j)$ 与区间所有点放在同一个集合中，去重后的元素个数，每次询问独立。

输入格式

一行两个整数 $n$ 和 $m$。

接下来一行 $n-1$ 个正数，第 $i$ 个数表示 $i+1$ 号节点的父亲。保证1号点是根节点。

接下来一行 $n$ 个正数，保证为 $1$ 到 $n$ 的排列。

接下来 $m$ 行，每行两个正数 $l, r$，表示询问的区间。

输出格式

一共 $m$ 行，每行一个整数表示答案。

样例

输入样例1：

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

输出样例1：

3
4

样例1解释：

第一次询问3、4、5三个点形成的虚树大小，显然是3。

第二次询问2、3、4三个点，还需要加上1号点，答案是4.

其他样例见下发文件。

数据范围

对于20%的数据， $n\leq100,m\leq100$ 。

对于40%的数据， $n\leq2e4,m\leq2e4$ 。

对于另外10%的数据，保证树的形态是链。

对于另外20%的数据，$\sum{r-l+1}\leq 5e6$

对于100%的数据， $n\leq5e4,m\leq5e4$ 。