题目描述

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

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

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

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

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

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

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

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

输入格式

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

输出格式

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

数据范围

样例输入

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$