题目描述

你是一个穷鬼，但你相信你的祖先里一定有有钱人。为此你去查了家谱得到一张家谱图。图里共有n个人，形成一个树结构。你将这些人按1~n编号，第i个人的身价为ai万元。1号是你能查到的最老的人，也就是其他所有人的祖先。剩下的n-1个人每人都有一个直系父亲（亲爹），第i个人的亲爹为pi（i=2..n）。现在你想知道m个问题的答案，每个问题的形式为：编号x的人及其不超过L代祖先中，最富有的那个人的身价是多少？约定每个人是自己的0代祖先，亲爹是自己的1代祖先，以此类推，只有具有直系关系的人才能称祖先。所以每个问题最多涉及L+1人，当然如果x的祖先总共不足L个，那么就求x及其所有祖先中的最高身价。

输入输出格式

输入格式

输入文件rich.in 第一行2个正整数n,m

第二行n-1个正整数p2..pn，其中pi表示第i个人的亲爹编号（父节点）。数据保证形成合法的树结构

第三行n个正整数a1..an，其中ai表示第i个人的身价

后面m行每行2个整数x,L，表示询问第x个人到其至多L代祖先（包含本人，至多L+1人）中的最高身价。如果x只有不到L个祖先，则问询其本人及所有祖先中的最高身价

输出格式

输出文件rich.out 输出m行每行1个正整数，对应一个问询的答案

输入输出样例

输入样例#1:

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

输出样例#1:

4
5
8

数据规模

40%的数据，n,m<=10

60%的数据，n,m<=100

100%的数据，n,m<=200000, 1<=ai<=1000000，1<=pi<n，1<=x<=n，0<=L<=n