E. Pass the Ball!
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Example
Input
4 4
2 4 1 3
1
2
3
4
Output
25
20
25
30
Note

The sample test case is explained below.

Round$$$b_1$$$$$$b_2$$$$$$b_3$$$$$$b_4$$$Answer
1314225
2432120
3241325
4123430