wjw 的银白森林

题目描述

在不知名的银白森林，共有 $n$ 个节点。

每个节点处，生活着一名魔法师。在每个节点，有一条通向其他节点的单向道路。

这天， wjw 被一阵神秘的力量所影响，落在了某个节点上，并且接下来 wjw 会沿着单向道路移动 $k$ 次。

每利用单向道路移动到一个节点时，这个节点处的魔法师会为 wjw 进行一次赐福，获得等于节点编号数量的祝福之力。（例如，当节点编号为 $3$ 时，经过这个节点可以获得 $3$ 点祝福之力）

注意，当重复经过某个节点时，魔法师是会多次为 wjw 进行赐福的。

而现在你提前掌握了整个银白森林的道路图，而 wjw 有可能被传送到某个节点 $x$，并且他将会移动 $k$ 步

你可以提前预测一下 wjw 会获得多少点祝福之力吗？

这样你就可以通过感应对应祝福之力的拥有者，将 wjw 救回来了！

输入格式

输入第一行包含两个整数 $n$ 和 $q$，表示银白森林有 $n$ 个节点，以及 $q$ 次询问 接下来一行包含 $n$ 个整数，第 $i$ 个数字 $a_i$ 表示节点 $i$ 的单向道路通向 $a_i$，允许 $a_i = i$ 接下来 $q$ 行 每行包含两个整数 $x,k$ 表示一次询问，询问当 wjw 被传送到 $x$ 节点并且移动 $k$ 次后会获得多少祝福之力

输出格式

对于每组询问输出 wjw 会获得的祝福之力数量

数据范围

测试数据

$n,q$

$k$

特殊性质

$1 \sim 2$

$1 \leq n,q \leq 10$

$1 \leq k \leq 100$

无

$3 \sim 4$

$1 \leq n,q \leq 100000$

$1 \leq k \leq 10^{12}$

$a_i=i+1$且$a_n=1$

$5 \sim 10$

无

样例输入

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

样例输出

11
29

样例解释

第一次询问是从 $1$ 出发移动 $5$ 次，路径为 $1 -> 2 -> 3 -> 1 -> 2 ->3$
获得的祝福之力为 $2+3+1+2+3=11$
第二次询问是从 $4$ 出发移动 $5$ 次，路径为 $4 -> 5 -> 6 -> 6 -> 6 ->6$
获得的祝福之力为 $5+6+6+6+6=29$