Toni 决定为 HONI（以及 COCI）出一道题。由于他不喜欢小孩子，他决定让这道题尽可能难。他想出了一个涉及不断变化的树的复杂问题，纯粹是为了让参赛者尽可能痛苦。

给定一棵无权树，包含 $N$ 个节点，树的根节点为 1。每个节点都有一个关联值 $v[i]$。树的结构由数组 $p[i]$ 定义，其中对于每个从 1 到 $N-1$ 的 $i$，$p[i]$ 表示 $i+1$ 的父节点。

对于树中的节点 $y$，函数 $f(y)$ 定义为： $$f(y) = \sum_{x \in S_y} d(x, y) \cdot v[x]$$ 其中 $d(x, y)$ 表示节点 $x$ 和 $y$ 之间的距离，$S_y$ 包含所有以 $y$ 为祖先的节点。

给定 $Q$ 次查询，每次查询包含两个节点 $x$ 和 $y$。对于每次查询，必须在树中模拟以下变换，并计算函数 $f(y)$：

1. 将所有以 $x$ 为子节点的节点连接到 $x$ 的父节点。
2. 从树中移除 $x$。
3. 将节点 $x$ 插回树中，位于 $y$ 和 $x$ 原本所在子树中 $y$ 的后代之间。

如果 $y$ 是 $x$ 的父节点，则树保持不变。始终满足 $x$ 在 $y$ 的子树中。对于每次查询，必须在根据上述过程临时修改树之后计算 $f(y)$ 的值。树的修改不是永久的，即每次查询后，树都会恢复到其原始状态。

输入格式

第一行包含两个整数 $N$ 和 $Q$ ($1 \le N, Q \le 5 \cdot 10^5$)，分别表示树的节点数和查询数。

第二行包含 $N$ 个整数 $v[i]$ ($1 \le v[i] \le 10^6$)，表示每个节点的值。

第三行包含 $N-1$ 个整数 $p[i]$ ($1 \le p[i] \le i$)，其中 $p[i]$ 表示节点 $i+1$ 的父节点。

接下来的 $Q$ 行，每行包含两个整数 $x$ 和 $y$ ($1 \le x, y \le N$)，表示上述操作中涉及的节点。

输出格式

在接下来的 $Q$ 行中，输出修改后的树上函数 $f(y)$ 的值。

子任务

样例

样例输入 1

3 1
1 2 3
1 2
1 2
3 1

样例输出 1

7

样例输入 2

3 2
4 5 6
1 1
2 1
3 1

样例输出 2

11
11

样例输入 3

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

样例输出 3

2
8
26

说明

第一个样例的说明：在对树应用操作后，节点 3 距离节点 1 的距离为 1，节点 2 距离节点 1 的距离为 2。结果为 $3 + 2 \cdot 2 = 7$。