W plemieniu C co 5 lat odbywa się wielka ceremonia ofiarna, podczas której arcykapłan recytuje zaklęcia nad starożytnym kręgiem runicznym, przywołując $n$ duszków. Duszki poruszają się szybko wzdłuż kierunków wyznaczonych przez krąg.
W każdym punkcie kręgu znajduje się symbol wskazujący na inny punkt. W następnej chwili duszek przeskakuje do wskazanego miejsca, a w kolejnej chwili przeskakuje zgodnie z symbolem znajdującym się w nowym miejscu. Duszki nigdy nie zderzają się ze sobą, co oznacza, że żadne dwa punkty nie wskazują na ten sam punkt.
Formalnie, jeśli symbol w punkcie $i$ wskazuje na $f(i)$, to pozycja duszka po $k$ chwilach wynosi $f_k(i) = f(f_{k-1}(i))$, gdzie $f_0(i) = i$.
Antropolog Z. Jack, który kiedyś prowadził tam badania, zapisał: „Członkowie plemienia C wierzą, że w dziwnym tańcu duszków można przepowiedzieć przyszłość”. Pozostawił on również zdjęcie dokumentujące to spektakularne wydarzenie.
Jednak wojny cywilizowanego świata zakłóciły spokój plemienia C, a ostrzał artyleryjski zniszczył dawny krąg runiczny. 50 lat później członkowie plemienia C proszą Cię o odtworzenie kręgu, ale runy na zdjęciu są zatarte.
Jedyną pozostałą wskazówką jest informacja od dawnego kapłana, że zdjęcie zostało wykonane w $k$-tej chwili od rozpoczęcia ceremonii. Na zdjęciu zaznaczono, skąd pierwotnie pochodził każdy duszek.
Pamięć kapłana jest dokładna, a zapiski Z. Jacka nie zawierają błędów, więc z pewnością uda Ci się znaleźć jeden z możliwych pierwotnych układów kręgu.
Wejście
Pierwsza linia zawiera dwie liczby całkowite $n, k$, oznaczające liczbę pozycji duszków w kręgu oraz czas trwania ceremonii.
W kolejnej linii znajduje się $n$ liczb całkowitych $1 \le p_i \le n$, oznaczających, że duszek, który pierwotnie znajdował się w punkcie $i$, dotarł do punktu $p_i$. Gwarantuje się, że dla $i \neq j$ zachodzi $p_i \neq p_j$.
Wyjście
Wypisz w jednej linii $n$ liczb, reprezentujących pierwotny krąg runiczny.
Zauważ, że może istnieć wiele poprawnych odpowiedzi; wystarczy wypisać dowolną z nich.
Przykład
Przykład 1
Wejście:
2 2 1 2
Wyjście:
2 1
Przykład 2
Wejście:
10 997 9 7 2 4 10 1 8 3 6 5
Wyjście:
9 7 2 4 10 1 8 3 6 5
Przykład 3
Patrz załączone pliki.
Przykład 4
Patrz załączone pliki.
Podzadania
| Testy | $n$ | $k$ | Specjalne ograniczenia |
|---|---|---|---|
| $1 \sim 3$ | $\leq 10$ | $k\leq 10$ | |
| $4 \sim 5$ | $\leq 2 \times 10^5$ | ||
| $6$ | $\leq 10^5$ | $=2$ | |
| $7 \sim 8$ | $=3$ | ||
| $9 \sim 12$ | $\leq 2 \times 10^5$ | $k$ jest liczbą pierwszą | |
| $13 \sim 15$ | Dla $i \ne n$ zachodzi $p_i = i+1$, $p_n = 1$ | ||
| $16 \sim 20$ |
Dla $100\%$ danych wejściowych gwarantuje się, że $n \le 10^5$ oraz $2 \le k \le 2 \times 10^5$.