Ball Passing Permutation Sum

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 (i.e. \(p_i \neq i\)). Moreover, after each round every child holds exactly one ball.

Initially, child \(i\) holds ball \(i\) (i.e. \(b_i=i\) for \(1\le i\le n\)). After \(k\) rounds, let \(b_i\) be the ball possessed by child \(i\). You are asked to process \(q\) queries. For each query given an integer \(k\), compute the value of \[ S = \sum_{i=1}^{n} i \times b_i, \] after \(k\) rounds.

Note: Since the passing process follows the permutation \(p\), you can observe that after \(k\) rounds the ball originally held by child \(j\) will be at child \(p^k(j)\) (where \(p^k\) denotes applying the permutation \(k\) times). Hence, the sum can also be written as \[ S = \sum_{j=1}^{n} j \times p^k(j). \]

inputFormat

The first line contains two integers \(n\) and \(q\) representing the number of children (and balls) and the number of queries.

The second line contains \(n\) space-separated integers \(p_1, p_2, \ldots, p_n\) describing the permutation. It is guaranteed that \(p_i \neq i\) for all \(1 \le i \le n\).

Each of the next \(q\) lines contains a single integer \(k\), representing the number of rounds.

outputFormat

For each query, output the value of \(\sum_{i=1}^{n} i \times b_i\) after \(k\) rounds on a separate line.

sample

3 2
2 3 1
0
1

14
11