结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

市彩票中心的摇奖大厅里有一台洗牌机。机器的滚筒上一周排开 $n$ 个格子，编号 $1 \sim n$；每天开机前，工作人员把编号 $1 \sim n$ 的 $n$ 颗摇奖球按号入格，即 $i$ 号格里放的是 $i$ 号球。

机器面板上贴着一张规则表，给出 $n$ 个整数 $f_1, f_2, \dots, f_n$，是 $1 \sim n$ 的一个排列。每摇一次，滚筒按规则表同时搬运全部球：$i$ 号格里的球被送到 $f_i$ 号格。由于规则表是排列，每次搬运后每个格子里仍恰好有一颗球。

质检科每年要对这台机器做周期检定，需要回答两个问题。第一，从球全部按号入格的状态开始，至少摇多少次，所有球才第一次全部回到各自的初始格子。第二，给定摇动次数 $T$，摇 $T$ 次之后，每个格子里各是几号球。

请编写检定程序：读入格子数 $n$、摇动次数 $T$ 与规则表，回答上述两问。

输入格式

从文件 shuffle.in 中读入数据。

• 第一行两个整数 $n, T$，分别表示格子数与摇动次数；
• 第二行 $n$ 个整数 $f_1, f_2, \dots, f_n$，表示规则表。

输出格式

输出到文件 shuffle.out 中。

• 第一行输出一个整数，表示第一问的答案；
• 第二行输出 $n$ 个整数，按格子编号 $1 \sim n$ 的顺序，依次表示摇 $T$ 次后每个格子里的球编号。

样例

4 2
2 3 1 4

3
2 3 1 4

样例 1 解释

逐摇记录各格子里的球编号：

摇第 $3$ 次时所有球第一次全部回到初始格子，故第一问答案为 $3$；摇 $2$ 次后的局面即第二行输出。

6 10
2 1 4 5 3 6

6
1 2 5 3 4 6

样例 2 解释

追踪 $3$ 号格里的球：它依次经过 $3$ 号格、$4$ 号格、$5$ 号格，每摇 $3$ 次回到 $3$ 号格一次。$10 = 3 \times 3 + 1$，故摇 $10$ 次后它在 $4$ 号格。$1$ 号格与 $2$ 号格的球每摇一次互换位置，$10$ 是偶数，摇 $10$ 次后各回原位。其余格子可同样推算。

5 7
1 2 3 4 5

1
1 2 3 4 5

样例 3 解释

每摇一次，$i$ 号格里的球都被送到 $i$ 号格，各球位置始终不变，摇 $1$ 次即第一次全部回到初始格子。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 10^5$，$0 \le T \le 10^{18}$；
• $f_1, f_2, \dots, f_n$ 是 $1 \sim n$ 的一个排列；
• 第一问的答案不超过 $10^{18}$。

各测试点的约束如下：

• 特殊性质 A：$1$ 号格里的球第一次重新回到 $1$ 号格，恰好发生在第 $n$ 次摇动。