우주 해적 Batch Compilation commands

먼, 먼 은하에 $1$ 이상 $N$ 이하의 번호가 붙은 $N$개의 고도로 문명화된 별들이 있습니다. 각 별은 하나의 텔레포터를 제공합니다. 각 텔레포터는 고정된 목적지를 가지고 있습니다. 우리는 이 텔레포터를 통해 단 하나의 방향으로 여행합니다.

은하계 황제 미술관은 은하계 내의 별들에서 미술 전시회를 엽니다. 이제 이 전시회는 1번 별에서 열립니다. 다음 전시회는 1번 별에서부터 텔레포터를 $K$번 이용했을 때 도착하는 별에서 개최됩니다.

우주 경찰은 우주 해적이 미술관의 소장품들을 훔칠 계획을 세우고 있다는 것을 발견했습니다. 우주 해적은 텔레포터 시스템에 침입하여, $a$번 별에 설치된 텔레포터의 목적지를 불법적으로 덮어쓸 것입니다. $a$번 별에 설치된 텔레포터의 목적지는 $b$번 별로 바뀝니다. 우주 해적은 단 하나의 별의 텔레포터 시스템에만 침입할 것입니다. 하지만, 우주 경찰은 $a, b$의 값을 찾을 수 없었습니다.

다음 전시회의 위치를 예측하기 위해, 우주 경찰은 각 $i$에 대해 다음 전시회가 $i$번 별에서 열리도록 하는 $(a, b)$의 쌍의 개수를 알고자 합니다. 이를 계산하는 것은 굉장히 어려운 일입니다. 여러분은 훌륭한 프로그래머이므로, 우주 경찰은 여러분에게 이를 계산하도록 요청했습니다.

해야 할 일

각 텔레포터의 목적지가 주어질 때, 각 $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)$는 여러분이 문제에 쓰여진 대로 $(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점]

추가 제약 조건이 없습니다.

예제 입력 및 출력

입력

5 7
5
1
4
3
2

출력

1
2
3
3
16

[그림 1]은 각 텔레포터의 목적지를 나타냅니다.

만약 $(a,b) = (1,4)$라면, 1번 별에 설치된 텔레포터의 목적지는 4번 별로 덮어 쓰일 것입니다. 각 텔레포터의 목적지는 [그림 2]와 같이 될 것입니다. 만약 우리가 1번 별에서 텔레포터를 7번 써서 여행한다면 4번 별에 도착할 것입니다. 따라서 다음 전시회는 4번 별에서 개최됩니다. (우리는 텔레포터들을 사용하여 $1 \rightarrow 4 \rightarrow 3 \rightarrow 4 \rightarrow 3 \rightarrow 4 \rightarrow 3 \rightarrow 4$와 같이 여행합니다.)

다음 전시회가 4번 별에서 개최되도록 하는 $(a, b)$의 쌍은 세 쌍 있습니다. ($(1, 4), (2, 4), (5, 3)$)

각 $(a, b)$ 쌍에 대해 다음 전시회가 개최될 위치는 다음 표에 요약되어 있습니다.

여러분이 $(a, b)$ 쌍의 수를 셀 때, $a = b$인 $(a, b)$ 쌍 역시 세어야 합니다. 여러분은 또한 텔레포터의 목적지가 변하지 않을 $(a, b)$의 쌍 역시 세어야 합니다.

입력

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