结论拍脸让人很不爽啊。如果我们的眼力不够好，该怎么发现这个结论呢？

显然有

$$f(p,q)\circ p=q$$ $$f(p,q)=q\circ p^{-1}$$

其中 $^{-1}$ 表示复合逆，即 $p^{-1}\circ p(i)=i,p\circ p^{-1}(i)=i$。

顺带一提，$(p\circ q)^{-1}=q^{-1}\circ p^{-1}$。

于是：

$$a_1=p$$ $$a_2=q$$ $$a_3=q\circ p^{-1}$$ $$a_4=q\circ p^{-1}\circ q^{-1}$$ $$a_5=q\circ p^{-1}\circ q^{-1}\circ p\circ q^{-1}$$ $$a_6=q\circ p^{-1}\circ q^{-1}\circ p\circ p \circ q^{-1}$$

可见每一步都是把上一个排列中的

• $p$ 换成 $q$，$p^{-1}$ 换成 $q^{-1}$；
• $q$ 换成 $q\circ p^{-1}$，$q^{-1}$ 换成 $p\circ q^{-1}$

另外可见有些前缀是“稳定的”，不会消失，比如：$q,qp^{-1},qp^{-1}q^{-1},qp^{-1}q^{-1}p$。

但是这就无法继续往下了，因为 $qp^{-1}q^{-1}p$ 这个串极其特殊，它在上面的变换下直接回到自身，一点也不多，它是完全“惰性”的，可以忽略掉它。

注意 $a_5$ 中我们已经造出了这样一个惰性串 $L$ 再加一个 $q^{-1}$，而这个 $q^{-1}$ 会变换为 $q\circ L^{-1}$，于是：

上面这个序列是“几乎周期”的，精确到“去掉惰性串”这一同构。

具体来说，$a_n=L\circ a_{n-6}\circ L^{-1}$。于是快速幂即可。

#include<bits/stdc++.h>
using namespace std;

int n;
struct pmt {
	int a[100005];
} p, q, L;

pmt inv(const pmt a) {
	pmt ans;
	for (int i = 0; i < n; i++) ans.a[a.a[i]] = i;
	return ans;
}
pmt operator *(const pmt a, const pmt b) {
	pmt ans;
	for (int i = 0; i < n; i++) ans.a[i] = a.a[b.a[i]];
	return ans;
}

pmt qpow(pmt a, int k) {
	pmt ans;
	for (int i = 0; i < n; i++) ans.a[i] = i;
	while (k) {
		if (k & 1) ans = ans * a;
		a = a * a;
		k >>= 1;
	}
	return ans;
}

int main() {
	int k; scanf("%d%d", &n, &k); k--;
	for (int i = 0; i < n; i++) scanf("%d", &p.a[i]), p.a[i]--;
	for (int i = 0; i < n; i++) scanf("%d", &q.a[i]), q.a[i]--;
	L = q * inv(p) * inv(q) * p;
	pmt ans;
	if (k % 6 == 0) ans = p;
	if (k % 6 == 1) ans = q;
	if (k % 6 == 2) ans = q * inv(p);
	if (k % 6 == 3) ans = L * inv(p);
	if (k % 6 == 4) ans = L * inv(q);
	if (k % 6 == 5) ans = L * p * inv(q);
	ans = qpow(L, k / 6) * ans * qpow(inv(L), k / 6);
	for (int i = 0; i < n; i++) printf("%d ", ans.a[i] + 1);
}