时间转换器（Time-Turner）是一种神奇的装置，可以用来回到过去，在过去待上一段时间，然后再回到现在。

Rose Granger 在霍格沃茨的图书馆里发现了一个时间转换器，她决定回到过去，带走布莱克（Black）家族的一些成员，以拯救麻瓜（没有魔法能力的人类）的生命。

布莱克家族共有 $n$ 名成员，按出生顺序编号为 $1$ 到 $n$。成员 $1$ 是布莱克家族有记载历史以来的第一位成员。对于每个 $i$（$2 \leqslant i \leqslant n$），成员 $i$ 是成员 $p_i$ 的直系后代（$1 \leqslant p_i < i$）。也就是说，成员 $p_i$ 以及他/她的所有祖先都是成员 $i$ 的祖先。书中还记载，布莱克家族的第 $i$ 位成员对 $c_i$ 名麻瓜的死亡负有责任。

现在 Rose 有 $q$ 个选项。第 $j$ 个选项是使用时间转换器回到过去，带走编号从 $a_j$ 到 $b_j$（$a_j \leqslant b_j$）的所有成员，然后回到现在。这一行动的结果是，任何在成员 $a_j$ 到 $b_j$ 中拥有祖先的布莱克家族成员都将永远不会出生。对于任何属于成员 $a_j$ 到 $b_j$（即 $a_j \leqslant i \leqslant b_j$）的成员 $i$，或者拥有属于成员 $a_j$ 到 $b_j$ 的祖先的成员 $i$，Rose 都将拯救 $c_i$ 条生命。

对于每个选项，请帮助 Rose 计算如果她采取该选项，她将拯救多少条生命。

输入格式

第一行包含两个整数 $n$ 和 $q$（$2 \leqslant n \leqslant 10^5$，$1 \leqslant q \leqslant 10^5$）。第二行包含 $n$ 个空格分隔的整数 $c_1$ 到 $c_n$（$0 \leqslant c_i \leqslant 10^4$）。第三行包含 $n-1$ 个整数 $p_2$ 到 $p_n$（$1 \leqslant p_i < i$）。接下来的 $q$ 行，每行包含一个选项；第 $j$ 行包含两个整数 $a_j$ 和 $b_j$（$1 \leqslant a_j \leqslant b_j \leqslant n$）。

输出格式

对于每个 $j$（$1 \leqslant j \leqslant q$），输出如果 Rose 采取第 $j$ 个选项，她将拯救的生命数量。

样例

输入 1

6 5
1 2 4 8 16 32
1 2 2 1 5
1 1
2 3
4 5
2 6
6 6

输出 1

63
14
56
62
32