因为在与嘟嘟的战争中失败，虚像被流放到了嘟南山挖玻矿。

嘟南山的结构是一棵以 $1$ 为根的树，每个结点 $i$ 有一个有关玻矿的一次函数 $f_i(x)=k_ix+b_i$。

为了帮助虚像挖出足够的玻矿嘟（南）山再起，你需要解决玻矿爆破的问题。

一共有 $q$ 次爆破工作，每次爆破有两个参数 $w,z$，你需要在树上选两个点 $u,v$，满足：

• $u$ 和 $v$ 的子树无交；
• $u,v$ 的子树分别和 $w$ 的子树有交；
• 爆破的甜度 $(f_u+f_v)(z)$ 最大。

你需要输出最大的甜度。若不存在合法的选择方案，输出 $0$。

输入格式

第一行，两个正整数 $n,q\ (3\le n\leq 2\times 10^5,1\leq q\le2\times10^5)$，表示嘟南山的大小和爆破的次数。

接下来一行，$n-1$ 个正整数 $f_2,f_3,\dots,f_n\ (1\le f_i< i)$，表示 $i$ 的父结点。

接下来 $n$ 行，每行两个整数 $k_i,b_i\ (|k_i|\leq 10^9,|b_i|\le 10^{18})$，表示每个结点上的一次函数。

接下来 $q$ 行，每行两个非负整数 $w_0,z_0$，表示每次爆破的参数。设上一次询问的答案模 $262144=2^{18}$ 的值为 $l$，上一次询问的答案模 $1073741824=2^{30}$ 的值为 $L$ ，本次询问的 $w=w_0\oplus l,z=z_0\oplus L$，其中 $\oplus$ 表示按位异或运算。$w,z$ 保证满足 $1\le w\le n,\ 0\le z\le 10^9$。保证对于给定的 $w,z$，至少存在一对符合条件的 $u,v$。

输出格式

$q$ 行，每行一个非负整数，表示每次爆破的最大甜度。

样例

输入

7 4
1 1 1 2 2 2
0 20
1 9
2 5
3 4
4 3
5 2
6 1
2 0
7 7
24 24
16 21

输出

5
25
17
47