题目描述

在不知名的银白之森，共有$n$个节点。每个节点处，生活着一名魔法师。在每个节点，有一条通向其他节点的单向道路。

不知道该说运气好还是不好，你被一阵神秘的力量所影响，落在了某个节点上。接下来你可以沿着这些单向道路移动$k$次。每利用单向道路移动到一个节点，这个节点处的魔法师会为你进行一次赐福，获得等于节点编号数量的命定之缘。（例如，当节点编号为3时，经过这个节点可以获得3个命定之缘）。

需要注意的是，反复经过同一个节点时，可以重复获得命定之缘。

非常幸运，你提前掌握了整个银白之森的道路图。但同时非常不幸，你会被神秘的力量丢到某个随机的节点上$q$次。那么，聪明如你，能求出来这$q$次移动分别能获得多少命定之缘吗？

输入格式

一行两个正整数$n$和$q$，表示银白之森总共有$n$个节点，编号为$1$到$n$。总共会有$q$次神秘力量。

接下来一行$n$个整数，第$i$个整数表示节点$i$处的单向道路通向哪个节点。（保证范围在$[1, n]$内，单向道路可以指向自己）

接下来$q$行，每行两个整数$x, k$，表示你该次神秘力量影响下落在了点$x$处，你可以沿着单向道路移动$k$次获得赐福。

输出格式

共$q$行，每行表示一次神秘力量影响下，你通过赐福获得的命定之缘的数量。

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

11
29

样例解释

第一次移动路径：1 -> 2 -> 3 -> 1 -> 2 -> 3

获得的命定之缘共计2 + 3 + 1 + 2 + 3 = 11

第二次移动路径：4 -> 5 -> 6 -> 6 -> 6 -> 6

获得的命定之缘共计5 + 6 + 6 + 6 + 6 = 29

数据规模与约定

每组数据点5分，共20组数据。

大样例

大样例下载