Перестановка довжини $$$n$$$ — масив довжини $$$n$$$, що містить всі значення від $$$1$$$ до $$$n$$$, і всі елементи якого попарно різні.
Подорослішавши й награвшись з масивом, Антон перейшов до вивчення цікавіших масивів — перестановок. Під час написання дипломної роботи перед ним постала дуже складна задача.
У нього є перестановка $$$p$$$ довжини $$$n$$$ та ціле число $$$k$$$. Він вирішив побудувати двовимірний масив $$$a$$$ з розмірами $$$(k+1) \times 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$$$.
3 22 1 3
3 3 6
5 35 3 1 4 2
10 9 8 12 6