跳转后标记求和

难度：T2

【知识点：倍增与二进制跳跃】

前置知识：本单元此前讲解的状态、边界与实现。

题目描述

每个站点有一个标记值，并指定唯一的后继站点。每次询问独立跳转，取结束位置的标记值。求所有询问得到的这些值之和，不累计途中经过的标记。

输入格式

第一行$n$、$q$；第二行每点唯一后继；第三行各点标记值；随后$q$行$s$、$k$。每次从$s$重新出发，只取跳$k$步后那个点的标记。

规则说明

第 $i$ 个后继编号表示：位于站点 $i$ 时，走一步就到这个编号的站点。每一步都按当前位置的后继继续跳转，可以回到已经经过的站点；走 $0$ 步时仍在起点。

输出格式

输出$q$次终点标记的总和；不是沿途标记和。

数据范围

$1\le n,q\le 100000$，标记绝对值≤$10^9$，$0\le k\le 10^9$，编号在$1$..$n$。

样例输入

1 6
1
-3
1 0
1 3
1 6
1 9
1 12
1 15

样例输出

-18

样例输入 2

4 3
2 3 4 2
10 20 30 40
1 0
1 3
2 4

样例输出 2

80

样例说明 2

三个终点是 $1,4,3$，只加它们的标记：$10+40+30=80$。