该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一颗以 $1$ 为根节点且有 $n$ 个节点的树，每个节点的值一开始是 $0$，有 $q$ 个操作，每个操作会给出 $p$, $v$ 意为将以 $p$ 为根节点的子树的所有节点的值都增加 $v$, 求每次操作后整棵树的所有点的值的最大值是多少。

输入格式

第一行包含两个整数 $n, q$ ($n = 2 \times 10^5, q = 2 \times 10^5$) —— 树的节点数以及询问数。

第二行包含 $n − 1$ 个整数 $f_2, f_3, . . . , f_n(f_i < i)$，意为每个节点的父节点。

接下来 $q$ 行每行包含 $2$ 个整数 $p_i, v_i$($1 \le p_i \le n$, $−1 \times 10^4 \le v_i \le 1 \times 10^4$)

输出格式

输出 $q$ 行，每行一个整数表示此时树里所有节点的值的最大值是多少。

样例

8 4
1 2 2 4 4 1 7
1 10
4 1
7 -1
4 -2

10
11
11
10