우주 해적

멀리 떨어진 은하에 $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$번 별이라는 뜻이다.

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

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

$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$이다.