题目描述

鸽子 Gimi 又惹上麻烦了。它正在游览一座城市，这座城市的道路结构是一棵有根树。树有 $N$ 个交叉口，编号为 $1$ 到 $N$，根为 $1$。城市中有 $N-1$ 条双向道路。对于每个交叉口 $i$，已知它的父亲 $p_i$，以及该交叉口处纪念碑的高度 $d_i$。

Gimi 将进行 $Q$ 次飞行。每次飞行从交叉口 $x$ 出发，沿着树上从 $x$ 到 $y$ 的简单路径依次经过所有交叉口，最后到达 $y$。

由于 Gimi 很笨拙，它会撞上路径中所有满足如下条件的纪念碑：该纪念碑高度大于等于此前在本次飞行中已经经过的所有纪念碑高度。也就是说，它会撞上路径上的“前缀最大值”位置，并且一定会撞上起点 $x$ 的纪念碑。

请对每次询问输出 Gimi 会撞上多少座纪念碑。

输入格式

第一行包含两个整数 $N,Q$。

第二行包含 $N$ 个整数：

第三行包含 $N-1$ 个整数：

其中 $p_i$ 表示点 $i$ 的父亲。

接下来 $Q$ 行，每行包含两个整数 $x_i,y_i$，表示一次询问。

输出格式

输出 $Q$ 行，第 $i$ 行表示第 $i$ 次飞行会撞上的纪念碑数量。

数据范围

• $1\le N\le 200000$；
• $1\le Q\le 200000$；
• $1\le p_i\le N$；
• $1\le d_i\le N$；
• 节点 $1$ 没有父亲。

子任务

样例

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

4
2
4
2
4
1
3
1
5

样例中，每次飞行经过的纪念碑高度序列分别为：

1 -> 1 -> 2 -> 3 -> 1
1 -> 3 -> 2 -> 1 -> 1
1 -> 1 -> 2 -> 3 -> 2
2 -> 3 -> 2 -> 1 -> 1
1 -> 1 -> 2 -> 3
3 -> 2 -> 1 -> 1
1 -> 2 -> 3
3 -> 2 -> 1
1 -> 1 -> 2 -> 3 -> 4

其中应统计每个序列中的前缀最大值出现次数。