#P17811. [ONTAK 2023]PER

[ONTAK 2023]PER

题目描述

给定 1,2,…,n1,2,\ldots,n 的一个排列 ff 和整数 kk,请构造一个排列 gg,使得对每个 xx 都有

$$g^k(x)=\underbrace{g(g(\cdots g}_{k\text{ 次}}(x)\cdots))=f(x).$$

如果不存在这样的排列,输出 -1。

输入格式

第一行包含 n,kn,k。第二行包含 f(1),f(2),…,f(n)f(1),f(2),\ldots,f(n),保证它们构成排列。

输出格式

有解时输出 g(1),g(2),…,g(n)g(1),g(2),\ldots,g(n);否则仅输出 -1。有多个解时可输出任意一个。

数据范围

1≤n≤1061\le n\le10^6,2≤k≤1092\le k\le10^9。

样例

4 6
2 1 4 3
4 3 1 2