在遥远的银河系中，有 $N$ 颗高度文明的星球，编号为 $1$ 到 $N$。每颗星球都提供一个传送器，每个传送器都有一个固定的目的地。我们只能沿一个方向通过传送器旅行。

银河帝国艺术博物馆在银河系的星球上举办艺术展览。现在展览在 1 号星球举行。下一次展览将在我们从 1 号星球出发，使用传送器旅行 $K$ 次后到达的星球举行。

太空警察发现一名太空海盗正计划窃取博物馆的藏品。太空海盗将侵入传送器系统，并非法覆盖 $a$ 号星球传送器的目的地。$a$ 号星球传送器的目的地将被修改为 $b$ 号星球。太空海盗只会侵入一颗星球的传送器系统。然而，太空警察无法确定 $a$ 和 $b$ 的确切值。

为了预测下一次展览的位置，太空警察想知道，对于每个 $i$，有多少对 $(a, b)$ 使得下一次展览将在 $i$ 号星球举行。计算这些数字是一项艰巨的任务。由于你是一名优秀的程序员，太空警察请求你来计算它们。

任务

给定每个传送器的目的地，对于每个 $i$，计算使得下一次展览在 $i$ 号星球举行的数对 $(a, b)$ 的数量。

输入格式

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

• 第一行包含两个空格分隔的整数 $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)$ 的数量。

说明

• $i$ 号星球传送器的目的地可能是 $i$ 号星球本身。在这种情况下，如果我们从 $i$ 号星球出发多次使用传送器，我们将停留在 $i$ 号星球。
• 即使 $a$ 号星球传送器的当前目的地已经是 $b$ 号星球，太空海盗也可能侵入传送器系统并将目的地覆盖为 $b$ 号星球。在这种情况下，$a$ 号星球传送器的目的地仍然是 $b$ 号星球；它不会改变。在计算满足题目描述条件的数对 $(a, b)$ 时，应包含此类数对。

数据范围

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

• $1 \le N \le 100\,000$
• $N \le K \le 10^{18}$

子任务

• 子任务 1 [10 分]：$N \le 100$
• 子任务 2 [37 分]：$N \le 3\,000$
• 子任务 3 [33 分]：$A_i \neq A_j$ ($1 \le i < j \le N$)
• 子任务 4 [20 分]：无附加限制

样例

样例输入 1

5 7
5
1
4
3
2

样例输出 1

1
2
3
3
16

图 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$。）

图 2、图 3、图 4

共有三对 $(a, b)$（即 $(1, 4), (2, 4), (5, 3)$）使得下一次展览在 4 号星球举行。

在计算数对 $(a, b)$ 的数量时，应计算 $a = b$ 的数对 $(a, b)$。你还应该计算传送器目的地未发生改变的数对 $(a, b)$。