Всі полюбляють перестановки#264
Перестановка довжини — масив довжини , що містить всі значення від до , і всі елементи якого попарно різні.
Подорослішавши й награвшись з масивом, Антон перейшов до вивчення цікавіших масивів — перестановок. Під час написання дипломної роботи перед ним постала дуже складна задача.
У нього є перестановка довжини та ціле число . Він вирішив побудувати двовимірний масив з розмірами (k+1) \times n.
a_{0j}=j для всіх (1 \leq j \leq n);
a_{ij}=a_{(i-1)p_j} для всіх (1 \leq i \leq k) та (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 | |||||
i=1 | |||||
i=2 | |||||
i=3 |
Для кожного (1 \leq x \leq n) він хоче знати суму усіх таких, що a_{ij}=x, де 1 \leq i \leq k. Іншими словами, він хоче знайти суму чисел — індексів числа у кожному a_i.
Розглянемо останній приклад. Якщо x=1, то відповідь буде 3+2+5=10.
Після обмірковувань і нескладних ідей, Антон впорався розв'язати цю задачу швидко. Тепер він хоче перевірити чи впораєтесь Ви розв'язати її.
Перший рядок вхідних даних містить два цілі числа , (1 \le n \le 10^6, 1 \le k \le 10^9) — довжина перестановки та кількість повторювань операцій відповідно.
Другий рядок містить в собі перестановку (1 \le p_i \le n).
Виведіть цілих чисел, де -те число — це відповідь для x=i.
Приклад
Приклад 1
( балів): k = 1;
( балів): p_i = i;
( балів): n \le 2000, k \le 2000;
( балів): n \le 2000, для будь-яких та існує таке , що p[p[p \dots p[i] \dots ]]=j, де таке вкладення береться разів;
( балів): для будь-яких та існує таке , що p[p[p \dots p[i] \dots ]]=j, де таке вкладення береться разів;
( балів): без додаткових обмежень.