Всі полюбляють перестановки
ліміт часу на тест
1 second
ліміт використання пам'яті на тест
256 megabytes
введення
standard input
виведення
standard output

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

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

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

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

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

$$$a_{ij}$$$$$$j=1$$$$$$j=2$$$$$$j=3$$$$$$j=4$$$$$$j=5$$$
$$$i=0$$$$$$1$$$$$$2$$$$$$3$$$$$$4$$$$$$5$$$
$$$i=1$$$$$$5$$$$$$3$$$$$$1$$$$$$4$$$$$$2$$$
$$$i=2$$$$$$2$$$$$$1$$$$$$5$$$$$$4$$$$$$3$$$
$$$i=3$$$$$$3$$$$$$5$$$$$$2$$$$$$4$$$$$$1$$$

Для кожного $$$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$$$.

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

Вхідні дані

Перший рядок вхідних даних містить два цілі числа $$$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$$$ балів): без додаткових обмежень.

Приклади

Вхідні дані
3 2
2 1 3
Вихідні дані
3 3 6 
Вхідні дані
5 3
5 3 1 4 2
Вихідні дані
10 9 8 12 6