H. 快速排列置换
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

对于一个长度为 $$$n$$$ 的整数序列 $$$[a_1, a_2, a_3, \cdots, a_n]$$$,如果其中 $$$1$$$ 到 $$$n$$$ 之间的每个数刚好出现一次,那么我们称它是一个长度为 $$$n$$$ 的排列。

例如,$$$[1, 3, 2, 4]$$$、$$$[1, 6, 2, 3, 4, 5]$$$、$$$[1]$$$ 都是排列,而 $$$[1, 1, 4]$$$ 不是。

对于两个长度同样为 $$$n$$$ 的排列 $$$a$$$ 和 $$$b$$$,我们定义 $$$b$$$ 对 $$$a$$$ 的排列置换 $$$F(a, b)$$$ 为:

$$$$$$ F(a, b) = [a_{b_1}, a_{b_2}, a_{b_3}, \cdots, a_{b_n}] $$$$$$

对于长度为 $$$n$$$ 的排列 $$$a$$$ 以及非负整数 $$$x$$$,我们定义 $$$a$$$ 的 $$$x$$$ 次自身置换 $$$G(a, x)$$$ 为:

$$$$$$ G(a, x) = \begin{cases} a & \text {if } x = 0\\ F \left ( G(a, x-1), G(a, x-1) \right ) &\text{else} \end{cases} $$$$$$

给定一个长度为 $$$n$$$ 的排列 $$$a$$$ 以及非负整数 $$$x$$$,请你计算并输出 $$$a$$$ 的 $$$x$$$ 次自身置换 $$$G(a, x)$$$。

Input

第一行包含一个整数 $$$n$$$($$$1 \leq n \leq 10^5$$$)。

第二行包含 $$$n$$$ 个整数 $$$a_1, a_2, a_3, \cdots, a_n$$$,用空格分隔,表示排列 $$$a$$$。

第三行包含一个整数 $$$x$$$($$$0 \leq x \leq 10^{10^5}$$$)。

Output

输出一行,包含 $$$n$$$ 个整数,用空格分隔,表示计算结果。

Examples
Input
5
2 3 1 5 4
3
Output
3 1 2 4 5
Input
12
9 7 8 1 2 3 12 6 11 5 4 10
1145141919810
Output
1 5 8 4 10 3 2 6 9 12 11 7