В племени C каждые 5 лет проводится грандиозный ритуал, во время которого верховный жрец читает заклинания над древним магическим кругом, призывая $n$ духов. Духи совершают быстрые прыжки по направлениям, указанным в круге.
В каждой позиции магического круга есть символ, указывающий на другую позицию. В следующий момент времени дух перемещается в указанную позицию, а затем, в следующий момент, прыгает дальше в соответствии с направлением, указанным в новой позиции. Духи никогда не сталкиваются, что означает, что никакие две позиции не указывают на одну и ту же позицию.
Формально, если символ в позиции $i$ указывает на $f(i)$, то позиция, в которой окажется дух через $k$ моментов времени, равна $f_k(i) = f(f_{k-1}(i))$, где $f_0(i) = i$.
Антрополог Z. Jack, который когда-то проводил там исследования, записал: «Жители племени C верят, что в странном танце духов можно предсказать будущее». Он также оставил фотографию, запечатлевшую это грандиозное зрелище.
Однако войны цивилизованного общества нарушили мир племени C, и артиллерийский огонь разрушил древний магический круг. Спустя 50 лет жители племени C попросили вас восстановить круг, но руны на фотографии стали неразборчивыми.
Осталось лишь несколько подсказок: жрец сообщил вам, что фотография была сделана в момент времени $k$ от начала ритуала. На фотографии отмечено, откуда изначально пришел каждый дух.
Память жреца точна, а записи Z. Jack верны, поэтому вы обязательно сможете найти один из возможных вариантов исходного магического круга.
Входные данные
В первой строке содержатся два целых числа $n$ и $k$, обозначающие количество позиций духов в магическом круге и время проведения ритуала.
В следующей строке содержатся $n$ целых чисел $1 \le p_i \le n$, означающих, что дух, который изначально находился в позиции $i$, в момент времени $k$ оказался в позиции $p_i$. Гарантируется, что для $i \neq j$ выполняется $p_i \neq p_j$.
Выходные данные
Выведите одну строку из $n$ чисел, представляющих исходный магический круг.
Обратите внимание, что может существовать несколько допустимых ответов, вам достаточно вывести любой из них.
Примеры
Пример 1
Входные данные
2 2 1 2
Выходные данные
2 1
Пример 2
Входные данные
10 997 9 7 2 4 10 1 8 3 6 5
Выходные данные
9 7 2 4 10 1 8 3 6 5
Пример 3
См. прилагаемые файлы.
Пример 4
См. прилагаемые файлы.
Подзадачи
| Тест | $n$ | $k$ | Особые ограничения |
|---|---|---|---|
| $1 \sim 3$ | $\le 10$ | $k\leq 10$ | |
| $4 \sim 5$ | $\le 2 \times 10^5$ | ||
| $6$ | $\le 10^5$ | $=2$ | |
| $7 \sim 8$ | $=3$ | ||
| $9 \sim 12$ | $\le 2 \times 10^5$ | $k$ — простое число | |
| $13 \sim 15$ | При $i \ne n$ $p_i = i+1$, $p_n = 1$ | ||
| $16 \sim 20$ |
Для $100\%$ данных гарантируется, что $n \le 10^5$, $2 \le k \le 2 \times 10^5$.