Mindenki Szereti a Permutációkat
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$.

  1. $$$a_{0j}=j$$$ minden $$$j$$$-re ($$$1 \leq j \leq n$$$);
  2. $$$a_{ij}=a_{(i-1)p_j}$$$ minden $$$i$$$-re ($$$1 \leq i \leq k$$$) és $$$j$$$-re ($$$1 \leq j \leq 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.

Input

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$$$).

Output

Nyomtass ki $$$n$$$ egész számot, ahol az $$$i$$$-edik szám a $$$x=i$$$ tartozó válasz.

Scoring

  1. ($$$8$$$ pont): $$$k = 1$$$;
  2. ($$$17$$$ pont): $$$p_i = i$$$;
  3. ($$$26$$$ pont): $$$n \le 2000, k \le 2000$$$;
  4. ($$$28$$$ pont): $$$n \le 2000$$$, bármely $$$i$$$ és $$$j$$$ esetén létezik egy $$$k$$$, úgy hogy $$$p[p[p \dots p[i] \dots ]]=j$$$, ahol a beágyazottság $$$k$$$-szor történik;
  5. ($$$9$$$ pont): bármely $$$i$$$ és $$$j$$$ esetén létezik egy $$$k$$$, úgy hogy $$$p[p[p \dots p[i] \dots ]]=j$$$, ahol a beágyazottság $$$k$$$-szor történik;
  6. ($$$12$$$ pont): további korlátozás nélkül.

Examples

Input
3 2
2 1 3
Output
3 3 6 
Input
5 3
5 3 1 4 2
Output
10 9 8 12 6