\begin{problem}{Всі полюбляють перестановки}{standard input}{standard output}{1 second}{256 megabytes}

Перестановка довжини $n$ --- масив довжини $n$, що містить всі значення від $1$ до $n$, і всі елементи якого попарно різні.

Подорослішавши й награвшись з масивом, Антон перейшов до вивчення цікавіших масивів --- перестановок. Під час написання дипломної роботи перед ним постала дуже складна задача. 

У нього є перестановка $p$ довжини $n$ та ціле число $k$. Він вирішив побудувати двовимірний масив $a$ з розмірами $(k+1) \times n$. 

\begin{enumerate}
\item $a_{0j}=j$ для всіх $j$ ($1 \leq j \leq n$);
\item $a_{ij}=a_{(i-1)p_j}$ для всіх $i$ ($1 \leq i \leq k$) та $j$ ($1 \leq j \leq n$).
\end{enumerate}

Нехай $p=[5, 3, 1, 4, 2]$ та $k=3$, тоді маємо наступний масив.

\begin{center}
\begin{tabular}{|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{tabular}
\end{center}

Для кожного $x$ ($1 \leq x \leq n$) він хоче знати суму усіх $j$ таких, що $a_{ij}=x$, де $1 \leq i \leq k$. Іншими словами, він хоче знайти суму $k$ чисел --- індексів числа $x$ у кожному $a_i$.

Розглянемо останній приклад. Якщо $x=1$, то відповідь буде $3+2+5=10$.

Після обмірковувань і нескладних ідей, Антон впорався розв'язати цю задачу швидко. Тепер він хоче перевірити чи впораєтесь Ви розв'язати її.


\InputFile
Перший рядок вхідних даних містить два цілі числа $n$, $k$ ($1 \le n \le 10^6$, $1 \le k \le 10^9$) --- довжина перестановки та кількість повторювань операцій відповідно.

Другий рядок містить в собі перестановку $p$ ($1 \le p_i \le n$).

\OutputFile
Виведіть $n$ цілих чисел, де $i$-те число --- це відповідь для $x=i$.

\Scoring
\begin{enumerate}
\item ($8$ балів): $k = 1$;
\item ($17$ балів): $p_i = i$;
\item ($26$ балів): $n \le 2000, k \le 2000$;
\item ($28$ балів): $n \le 2000$, для будь-яких $i$ та $j$ існує таке $k$, що $p[p[p \dots p[i] \dots ]]=j$, де таке вкладення береться $k$ разів;
\item ($9$ балів): для будь-яких $i$ та $j$ існує таке $k$, що $p[p[p \dots p[i] \dots ]]=j$, де таке вкладення береться $k$ разів;
\item ($12$ балів): без додаткових обмежень.
\end{enumerate}

\Examples

\begin{example}
\exmpfile{example.01}{example.01.a}%
\exmpfile{example.02}{example.02.a}%
\end{example}

\end{problem}

