Всі полюбляють перестановки

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

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

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

1. $a_{0j}=j$ для всіх $j$ ($1\le j\le n$);

2. $a_{ij}=a_{(i-1)p_j}$ для всіх $i$ ($1\le i\le k$) та $j$ ($1\le j\le n$).

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

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

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

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

Вхідні дані

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

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

Вихідні дані

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

Приклади

Оцінювання

1. ($8$ балів): $k=1$;

2. ($17$ балів): $p_i=i$;

3. ($26$ балів): $n\le 2000,k\le 2000$;

4. ($28$ балів): $n\le 2000$, для будь-яких $i$ та $j$ існує таке $k$, що $p[p[p\dots p[i]\dots ]]=j$, де таке вкладення береться $k$ разів;

5. ($9$ балів): для будь-яких $i$ та $j$ існує таке $k$, що $p[p[p\dots p[i]\dots ]]=j$, де таке вкладення береться $k$ разів;

6. ($12$ балів): без додаткових обмежень.