우주 해적 | cho.sh

멀리 떨어진 은하에 $1$ 번부터 $N$ 번까지 번호가 붙은 별이 $N$ 개 있다. 별마다 순간이동 장치가 하나씩 있고, 장치마다 목적지가 되는 별이 하나로 정해져 있다. 순간이동은 정해진 방향으로만 일어난다.

은하 미술관은 이 별들에서 전시회를 연다. 지금 전시회는 $1$ 번 별에서 열리고 있다. 다음 전시회는 $1$ 번 별에서 순간이동을 $K$ 번 해서 도착하는 별에서 열린다.

우주 경찰은 우주 해적이 미술관 소장품을 노리고 있다는 사실을 알아냈다. 해적은 순간이동 장치 시스템에 침입해 $a$ 번 별에 있는 장치의 목적지를 $b$ 번 별로 덮어쓴다. 해적이 침입하는 별은 하나뿐이지만, 경찰은 $a$ 와 $b$ 의 값을 알아내지 못했다.

다음 전시회 장소를 예측하려고, 경찰은 각 $i$ 마다 다음 전시회가 $i$ 번 별에서 열리게 만드는 순서쌍 $(a, b)$ 가 몇 개인지 알고 싶다.

각 순간이동 장치의 목적지가 주어질 때, 각 $i$ 에 대해 그 개수를 구하라.

첫째 줄에 $N$ 과 $K$ 가 공백으로 구분되어 주어진다. 은하에 별이 $N$ 개 있고, 다음 전시회는 $1$ 번 별에서 순간이동을 $K$ 번 한 뒤 도착하는 별에서 열린다는 뜻이다.

이어지는 $N$ 개 줄 중 $i$ 번째 줄에는 정수 $A_i$ 가 주어진다. $i$ 번 별에 있는 순간이동 장치의 현재 목적지가 $A_i$ 번 별이라는 뜻이다.

모든 입력은 다음 조건을 만족한다.

$N$ 개 줄을 출력한다. $i$ 번째 줄에는 다음 전시회가 $i$ 번 별에서 열리게 만드는 순서쌍 $(a, b)$ 의 개수를 출력한다.

$i$ 번 별에 있는 장치의 목적지가 $i$ 번 별 자신일 수도 있다. 이때는 $i$ 번 별에서 순간이동을 몇 번 하든 계속 $i$ 번 별에 머무른다.

$a$ 번 별에 있는 장치의 현재 목적지가 이미 $b$ 번 별이더라도, 해적은 그 목적지를 $b$ 번 별로 덮어쓸 수 있다. 이 경우 목적지는 $b$ 번 별 그대로이고 바뀌지 않는다. 이런 순서쌍 $(a, b)$ 도 개수에 넣는다.

$a = b$ 인 순서쌍도 센다. 즉 $1 \le a \le N$ , $1 \le b \le N$ 을 만족하는 순서쌍 $N^2$ 개를 모두 따지므로, 출력하는 $N$ 개 수의 합은 언제나 $N^2$ 이다.