Description

In a galaxy far, far away,... there are $N$ highly civilized stars numbered from 1 to $N$. Each star provides one teleporter. Each teleporter has a fixed destination. We travel through a teleporter only in one direction.

The Galactic Empire Museum of Art holds art exhibitions in stars in the galaxy. Now the exhibition is held in the star 1. The next exhibition will be held in the star where we travel from the star 1 using the teleporters $K$ times.

The Space Police found that a space pirate is planning to steal collections of the museum. The space pirate will crack into the teleporter system, and illegally overwrite the destination of the teleporter in the star $a$. The destination of the teleporter in the star $a$ will be modified to the star $b$. The space pirate will crack into the teleporter system of one star only. However, the Space Police could not find the precise values of $a, b$.

In order to predict the location of the next exhibition, the Space Police would like to know, for each $i$, the number of pairs $(a,b)$ such that the next exhibition will be held in the star $i$. To calculate these numbers is a difficult job. Since you are a good programmer, the Space Police asked you to calculate them.

Task

Given the destination of each teleporter, for each $i$, calculate the number of pairs $(a,b)$ such that the next exhibition will be held in the star $i$.

Input Format

Read the following data from the standard input.

• The first line of input contains two space separated integers $N$ and $K$. This means there are $N$ stars in the galaxy, and the next exhibition will be held in the star where we travel from the star 1 using the teleporters $K$ times.
• The $i$-th line ($1 \le i \le N$) of the following $N$ lines contains an integer $A_i$ ($1 \le A_i \le N$). This means the current destination of the teleporter in the star $i$ is the star $A_i$.

Output Format

Write $N$ lines to the standard output. The $i$-th line ($1 \le i \le N$) should contain an integer, the number of pairs $(a,b)$ such that the next exhibition will be held in the star $i$.

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

Hint

Sample 1 Explanation

The destination of each teleporter is described in Figure 1.

:::align{center}

Figure 1 :::

If $(a,b) = (1,4)$, the destination of the teleporter in the star 1 will be overwritten to the star 4. The destination of each teleporter will become as in Figure 2. We will arrive at the star 4 if we travel from the star 1 using the teleporters 7 times. Therefore, the next exhibition will be held in the star 4. (We travel as $1 \to 4 \to 3 \to 4 \to 3 \to 4 \to 3 \to 4$ using the teleporters.)

:::align{center} :::

There are three pairs of $(a,b)$ (i.e. $(1,4)$, $(2,4)$, $(5,3)$) where the next exhibition will be held in the star 4. The location of the next exhibition for each pair $(a,b)$ is summarized in the following table.

When you count the number of pairs $(a,b)$, the pairs $(a,b)$ with $a = b$ should be counted. You should also count the pairs $(a,b)$ such that the destination of the teleporter will not be changed.

Note

• The destination of the teleporter in the star $i$ may be the star $i$ itself. In this case, we will stay in the star $i$ if we travel from the star $i$ using the teleporter many times.
• Even if the current destination of the teleporter in the star $a$ is the star $b$, the space pirate may crack into the teleporter system and overwrite the destination to be the star $b$. In this case, the destination of the teleporter in the star $a$ will still be the star $b$; it will not be changed. Such pairs $(a,b)$ should be included when you count the number of pairs $(a,b)$ satisfying the conditions in the task statement.

Constraints

All input data satisfy the following conditions.

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

Subtask

Subtask 1 [10 points]

• $N \le 100$.

Subtask 2 [37 points]

• $N \le 3000$.

Subtask 3 [33 points]

• $A_i \ne A_j$ for all $1 \le i < j \le N$.

Subtask 4 [20 points]

There are no additional constraints.