说明

在很久很久以前，在一个遥远的星系里……有 $N$ 颗高度文明的恒星，编号从 1 到 $N$。每颗恒星上都有一个传送门。每个传送门都有一个固定的目的地。我们只能沿着传送门的指向单向旅行。

银河帝国艺术博物馆会在星系中的恒星上举办艺术展。现在，展览正在恒星 1 上举行。下一场展览将在从恒星 1 出发，使用传送门旅行 $K$ 次后到达的恒星上举办。

太空警察发现，有个太空海盗计划窃取博物馆的藏品。这名海盗将入侵传送门系统，非法篡改恒星 $a$ 上传送门的目的地。恒星 $a$ 上传送门的目的地将被修改为恒星 $b$。该海盗只会入侵并修改一颗恒星的传送门系统。然而，太空警察无法确定 $a$ 和 $b$ 的具体值。

为了预测下一场展览的位置，太空警察希望知道，对于每个 $i$，有多少对 $(a, b)$ 使得下一场展览会在恒星 $i$ 举办。计算这些数值是一项艰巨的任务。鉴于你是一位优秀的程序员，太空警察请求你帮忙计算。

任务

给定每个传送门的当前目的地，对于每个 $i$，计算有多少对 $(a, b)$ 使得下一场展览会在恒星 $i$ 举办。

输入格式

从标准输入读取以下数据。

• 输入的第一行包含两个以空格分隔的整数 $N$ 和 $K$。这表示星系中有 $N$ 颗恒星，下一场展览将在从恒星 1 出发，使用传送门旅行 $K$ 次后到达的恒星上举办。
• 接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含一个整数 $A_i$（$1 \le A_i \le N$）。这表示当前恒星 $i$ 上传送门的目的地是恒星 $A_i$。

输出格式

向标准输出写入 $N$ 行。第 $i$ 行（$1 \le i \le N$）应输出一个整数，表示使得下一场展览会在恒星 $i$ 举办的对 $(a, b)$ 的数量。

5 7
5
1
4
3
2

1
2
3
3
16

40 57
9
24
1
28
29
5
9
1
36
5
35
14
14
29
28
34
28
4
34
36
33
11
22
23
10
18
26
33
36
15
37
31
27
16
25
37
6
31
21
31

4
2
1
12
18
9
1
1
15
0
4
0
0
2
0
11
0
12
0
2
0
0
1
0
5
12
13
13
34
0
5
1
15
10
8
1351
36
1
0
1

提示

样例 1 解释

每个传送门的目的地如图 1 所示。

:::align{center}

图 1 :::

如果 $(a, b) = (1, 4)$，恒星 1 上传送门的目的地会被篡改为恒星 4。每个传送门的目的地将变成如图 2 所示。若从恒星 1 出发，使用传送门旅行 7 次，我们将到达恒星 4。因此，下一场展览将在恒星 4 举办。（旅行路径为：$1 \to 4 \to 3 \to 4 \to 3 \to 4 \to 3 \to 4$）。

:::align{center} :::

有三对 $(a, b)$（即 $(1,4)$、$(2,4)$、$(5,3)$）使得下一场展览在恒星 4 举办。对于每对 $(a, b)$，下一场展览的位置总结如下表。

在计数 $(a, b)$ 对的数量时，$a = b$ 的情况也应计入。此外，即使传送门目的地实际上未被改变（即修改前后的目的地相同），对应的对 $(a, b)$ 也应被计入。

注意

• 恒星 $i$ 上传送门的目的地可以是恒星 $i$ 本身。在这种情况下，如果从恒星 $i$ 出发多次使用传送门，我们将一直停留在恒星 $i$。
• 即使恒星 $a$ 上传送门的当前目的地已经是恒星 $b$，太空海盗仍然可能入侵传送门系统并将目的地覆写为恒星 $b$。在这种情况下，恒星 $a$ 上传送门的目的地保持不变。在计算满足题目描述条件的 $(a, b)$ 对时，这类情况也应包含在内。

约束条件

所有输入数据满足以下条件。

• $1 \le N \le 100000$。
• $N \le K \le 10^{18}$。

子任务

子任务 1 [10 分]

• $N \le 100$。

子任务 2 [37 分]

• $N \le 3000$。

子任务 3 [33 分]

• 对于所有 $1 \le i < j \le N$，满足 $A_i \ne A_j$。

子任务 4 [20 分]

• 无额外约束。

翻译由 DeepSeek V3.2 完成