Egy $$$n$$$ hosszúságú permutáció egy $$$n$$$ hosszúságú tömb, amely tartalmazza az összes egészet $$$1$$$-től $$$n$$$-ig, és minden eleme páronként különböző.
Anton, aki gyermekkorát tömbökkel játszva töltötte, most érdekesebb tömbök tanulmányozására tért át — permutációkra. Amikor értekezését írta, nagyon nehéz feladattal szembesült.
Adott egy $$$n$$$ hosszúságú permutáció, $$$p$$$, és egy egész szám, $$$k$$$. Úgy döntött, hogy létrehoz egy kétdimenziós tömböt, $$$a$$$ mérettel $$$(k+1) \times n$$$.
Legyen $$$p=[5, 3, 1, 4, 2]$$$ és $$$k=3$$$, ekkor az alábbi tömböt kapjuk.
$$$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$$$ |
Minden $$$x$$$-re ($$$1 \leq x \leq n$$$), szeretné tudni az összes olyan $$$j$$$ összegét, ahol $$$a_{ij}=x$$$, ahol $$$1 \leq i \leq k$$$. Más szóval, szeretné megtalálni $$$k$$$ szám összegét — a szám $$$x$$$ indexeit minden $$$a_i$$$-ben.
Tekintsük az előző példát. Ha $$$x=1$$$, akkor a válasz $$$3+2+5=10$$$ lesz.
Némi tanakodás és egyszerű ötletek után Anton gyorsan megoldotta ezt a problémát. Most azt szeretné tudni, hogy te is meg tudod-e oldani.
A bemenet első sorában két egész szám található, $$$n$$$, $$$k$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le k \le 10^9$$$) — a permutáció hossza és az ismétlési műveletek száma.
A második sor tartalmazza a permutációt, $$$p$$$ ($$$1 \le p_i \le n$$$).
Nyomtass ki $$$n$$$ egész számot, ahol az $$$i$$$-edik szám a $$$x=i$$$ tartozó válasz.
3 22 1 3
3 3 6
5 35 3 1 4 2
10 9 8 12 6