题目描述

There are $n$ children playing with $n$ balls. Both children and balls are numbered from $1$ to $n$.

Before the game, $n$ integers $p_1, p_2, \cdots, p_n$ are given. In each round of the game, child $i$ will pass the ball he possesses to child $p_i$. It is guaranteed that no child will pass his ball to himself, which means $p_i \neq i$. Moreover, we also know that after each round, each child will hold exactly one ball.

Let $b_i$ be the ball possessed by child $i$. At the beginning of the game, child $i$ ($1 \le i \le n$) will be carrying ball $i$, which means $b_i=i$ initially. You're asked to process $q$ queries. For each query you're given an integer $k$ and you need to compute the value of $\sum\limits_{i=1}^{n} i \times b_i$ after $k$ rounds.

输入格式

There is only one test case for each test file.

The first line of the input contains two integers $n$ ($2 \le n \le 10^5$) and $q$ ($1 \le q \le 10^5$), indicating the number of children and the number of queries.

The second line contains $n$ integers $p_1, p_2, \cdots, p_n$ ($1 \le p_i \le n$) indicating how the children pass the balls around.

For the following $q$ lines, the $i$-th line contains one integer $k_i$ ($1 \le k_i \le 10^9$) indicating a query asking for the result after $k_i$ rounds.

输出格式

For each query output one line containing one integer indicating the answer.

题目大意

【题目描述】

有 $n$ 个孩子和 $n$ 个球在玩游戏。孩子和球都从 $1$ 编号到 $n$。

游戏开始前，给出了 $n$ 个整数 $p_1, p_2, \cdots, p_n$。在游戏的每一轮中，孩子 $i$ 会把他手里的球传给孩子 $p_i$。保证没有孩子会把他手里的球传给自己，也就是说 $p_i \neq i$。此外，我们还知道在每一轮之后，每个孩子手里都会正好持有一个球。

设 $b_i$ 表示孩子 $i$ 所持有的球。在游戏开始时，孩子 $i$（$1 \le i \le n$）将携带球 $i$，也就是说 $b_i=i$。你需要处理 $q$ 个查询。对于每个查询，你会得到一个整数 $k$，你需要计算在 $k$ 轮后 $\sum\limits_{i=1}^{n} i \times b_i$ 的值。

【输入格式】

输入的第一行包含两个整数 $n$（$2 \le n \le 10^5$）和 $q$（$1 \le q \le 10^5$），表示孩子的数量和查询的数量。

第二行包含 $n$ 个整数 $p_1, p_2, \cdots, p_n$（$1 \le p_i \le n$），表示孩子之间传球的方式。

接下来的 $q$ 行中，第 $i$ 行包含一个整数 $k_i$（$1 \le k_i \le 10^9$），表示询问在 $k_i$ 轮后的结果。

【输出格式】

对于每个查询，输出一行包含一个整数，表示答案。

【样例解释】

示例测试用例解释如下。

$$\begin{array}{|c|c|c|c|c|c|} \hline \textbf{轮次} & \textbf{b1} & \textbf{b2} & \textbf{b3} & \textbf{b4} & \textbf{答案} \\\hline 1 & 3 & 1 & 4 & 2 & 25 \\\hline 2 & 4 & 3 & 2 & 1 & 20 \\\hline 3 & 2 & 4 & 1 & 3 & 25 \\\hline 4 & 1 & 2 & 3 & 4 & 30 \\\hline \end{array} $$

翻译来自于：ChatGPT。

4 4
2 4 1 3
1
2
3
4

25
20
25
30

提示

The sample test case is explained below.

$$\begin{array}{|c|c|c|c|c|c|} \hline \textbf{Round} & \textbf{b1} & \textbf{b2} & \textbf{b3} & \textbf{b4} & \textbf{Answer} \\\hline 1 & 3 & 1 & 4 & 2 & 25 \\\hline 2 & 4 & 3 & 2 & 1 & 20 \\\hline 3 & 2 & 4 & 1 & 3 & 25 \\\hline 4 & 1 & 2 & 3 & 4 & 30 \\\hline \end{array} $$