AT_abc438_e.[ABC438E] Heavy Buckets

有 $N$ 人和 $N$ 桶。人和水桶的编号都是 $1, 2, \ldots, N$ 。

最初，人 $i$ 只持有水桶 $i$ ，而水桶 $i$ 是空的。

从现在起，将执行以下操作 $10^9$ 次：

• 同时在 $i = 1, 2, \ldots, N$ 中， $i$ 将 $i$ 个单位的水添加到自己手中的每个水桶中，并将这些水桶递给 $A_i$ 。

在这里，水桶中的水量没有限制。

对于 $i = 1, 2, \ldots, Q$ ，请回答下列问题：

• 求第 $T_i$ 次操作后，水桶 $B_i$ 中的水量。

输入内容由标准输入法提供，格式如下

$N$ $Q\\$
$A_1$ $A_2$ $\ldots$ $A_N\\$
$T_1$ $B_1\\$
$T_2$ $B_2\\$
$\vdots\\$
$T_Q$ $B_Q$

输出 $Q$ 行。第 $i$ 行应包含第 $i$ 次查询的答案。

数据范围

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq A_i \leq N$
• $1 \leq T_i \leq 10^9$
• $1 \leq B_i \leq N$
• 所有输入值均为整数。

样例解释

我们将解释第一个查询。

最初，邮筒 $3$ 由 $3$ 持有。

在进行第 $1$ 次操作后，水桶 $3$ 被 $2$ 持有，并包含 $3$ 个单位的水。

紧接着第 $2$ 次操作之后，水桶 $3$ 被人 $4$ 持有，里面有 $5$ 个单位的水。

紧接着第 $3$ 次操作之后，水桶 $3$ 被人 $2$ 持有，里面有 $9$ 个单位的水。

在第 $4$ 次操作之后，水桶 $3$ 被 $4$ 人持有，里面有 $11$ 个单位的水。

因此，第一个问题的答案是 $11$ 。