Description

终于，同学们把布丁做好了。最爱吃布丁的茅野开始想，这个布丁有多好吃呢？

一个布丁的好吃程度，取决于里面的改变口味的食材。材料不同的话，颜色和美味度也是不一样的。

布丁里面有 $n$ 种调味食材，有 $n-1$ 个东西连接着，第一种食材在最上面，相当于这一棵树的根。

现在，茅野制定一个布丁的好吃程度与指定的某两个值 $u,k$ 有关，这个好吃程度为，第 $u$ 种食材的 $k$ 级祖先 $v$ 食材的所有 $k$ 级儿子与 $v$ 食材颜色相同的那些 $k$ 级儿子的美味度之和。可以发现，$u$ 或者 $k$ 不同，一般情况下美味度是不同的。所以有 $q$ 个问题想要问你。

特殊地，如果第 $u$ 种食材没有 $k$ 级祖先，直接输出 $0$ 即可。

Input Format

第一行两个整数 $n,q$，表示有 $n$ 个食材，$q$ 个询问。

第二行 $n$ 个整数，第 $i$ 个整数表示食材 $i$ 的颜色 $color_i$。

第三行 $n$ 个整数，第 $i$ 个整数表示食材 $i$ 的美味值 $d_i$。

第四行 $n-1$ 个整数，第 $i$ 个整数表示食材 $i+1$ 的父节点 $fa_i$。

接下来 $q$ 行，每行两个整数 $u,k$ 表示询问。

Output Format

有 $q$ 行，每行一个整数，表示询问的结果。

3 1
1 1 1
1 2 3
1 1
2 1

5

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

0
6
0

Hint

样例解释 #1

食材 $2$ 的 $1$ 级祖先是食材 $1$，食材 $1$ 的 $1$ 级儿子有食材 $2$ 与食材 $3$，食材 $2$ 与食材 $3$ 的颜色都与食材 $1$ 的颜色相同，所以美味度之和为 $2+3=5$。

数据范围

本题采用捆绑测试。

• Subtask 1（30 points），鸡蛋缺乏，布丁不大：$n \leq 10^3$，$q \leq 10^4$。
• Subtask 2（20 points），食材构成了一条链：$n \leq 5 \times 10^5$，$q \leq 10^5$，$color_i \leq 10^2$。
• Subtask 3（50 points）：数据无特殊限制。

对于 $100\%$ 的数据，$1 \leq n,q,color_i \leq 5 \times 10^5$，$1 \leq d_i \leq 10^5$。

提示

第二个子任务中的测试点与第三个子任务中的测试点时限 2S。