Everyone Loves Permutations#264
A permutation of length is an array of length containing all integers from to , and all its elements are pairwise distinct.
Having grown up and played with arrays, Anton moved on to studying more interesting arrays — permutations. While writing his thesis, he faced a very difficult task.
He has a permutation of length and an integer . He decided to construct a two-dimensional array with sizes (k+1) \times n.
a_{0j}=j for all (1 \leq j \leq n);
a_{ij}=a_{(i-1)p_j} for all (1 \leq i \leq k) and (1 \leq j \leq n).
Let p=[5, 3, 1, 4, 2] and k=3, then we have the following array.
a_{ij} | j=1 | j=2 | j=3 | j=4 | j=5 |
i=0 | |||||
i=1 | |||||
i=2 | |||||
i=3 |
For each (1 \leq x \leq n), he wants to know the sum of all such that a_{ij}=x, where 1 \leq i \leq k. In other words, he wants to find the sum of numbers — the indices of the number in each a_i.
Consider the last example. If x=1, the answer will be 3+2+5=10.
After some deliberation and simple ideas, Anton managed to solve this problem quickly. Now he wants to check if you can solve it too.
The first line of the input contains two integers , (1 \le n \le 10^6, 1 \le k \le 10^9) — the length of the permutation and the number of repetitions of operations, respectively.
The second line contains the permutation (1 \le p_i \le n).
Print integers, where the -th number is the answer for x=i.
Example
Example 1
( points): k = 1;
( points): p_i = i;
( points): n \le 2000, k \le 2000;
( points): n \le 2000, for any and , there exists a such that p[p[p \dots p[i] \dots ]]=j, where the nesting is taken times;
( points): for any and , there exists a such that p[p[p \dots p[i] \dots ]]=j, where the nesting is taken times;
( points): without additional restrictions.