Problem G
Pass the Ball!
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.
Input
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.
Output
For each query output one line containing one integer indicating the answer.
Sample Explanation
The sample test case is explained below.
|
Round |
$b_1$ |
$b_2$ |
$b_3$ |
$b_4$ |
Answer |
|
1 |
3 |
1 |
4 |
2 |
25 |
|
2 |
4 |
3 |
2 |
1 |
20 |
|
3 |
2 |
4 |
1 |
3 |
25 |
|
4 |
1 |
2 |
3 |
4 |
30 |
| Sample Input 1 | Sample Output 1 |
|---|---|
4 4 2 4 1 3 1 2 3 4 |
25 20 25 30 |