题目描述

A permutation of length $n$ is an array of length $n$ containing all integers from $1$ to $n$, 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 $p$ of length $n$ and an integer $k$. He decided to construct a two-dimensional array $a$ with sizes $(k+1) \times n$.

• $a_{0j}=j$ for all $j$ ($1 \leq j \leq n$);
• $a_{ij}=a_{(i-1)p_j}$ for all $i$ ($1 \leq i \leq k$) and $j$ ($1 \leq j \leq n$).

Let $p=[5, 3, 1, 4, 2]$ and $k=3$, then we have the following array.

$$\begin{array}{|c|c|c|c|c|c|} \hline a_{ij} & j=1 & j=2 & j=3 & j=4 & j=5 \\ \hline\hline i=0 & 1 & 2 & 3 & 4 & 5 \\ \hline i=1 & 5 & 3 & 1 & 4 & 2 \\ \hline i=2 & 2 & 1 & 5 & 4 & 3 \\ \hline i=3 & 3 & 5 & 2 & 4 & 1 \\ \hline \end{array}$$

For each $x$ ($1 \leq x \leq n$), he wants to know the sum of all $j$ such that $a_{ij}=x$, where $1 \leq i \leq k$. In other words, he wants to find the sum of $k$ numbers --- the indices of the number $x$ 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 $n$, $k$ ($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 $p$ ($1 \le p_i \le n$).

输出格式

Print $n$ integers, where the $i$-th number is the answer for $x=i$.

3 2
2 1 3

3 3 6

5 3
5 3 1 4 2

10 9 8 12 6

提示

• ($8$ points): $k = 1$;
• ($17$ points): $p_i = i$;
• ($26$ points): $n \le 2000, k \le 2000$;
• ($28$ points): $n \le 2000$, for any $i$ and $j$, there exists a $k$ such that $p[p[p \dots p[i] \dots ]]=j$, where the nesting is taken $k$ times;
• ($9$ points): for any $i$ and $j$, there exists a $k$ such that $p[p[p \dots p[i] \dots ]]=j$, where the nesting is taken $k$ times;
• ($12$ points): without additional restrictions.