Trong một thiên hà xa xôi có \(N\) hành tinh, được đánh số từ \(1\) đến \(N\). Mỗi hành tinh có đúng một máy dịch chuyển với đích đến cố định, và máy dịch chuyển chỉ hoạt động theo một chiều.

Triển lãm hiện tại của Bảo tàng Nghệ thuật Đế quốc Thiên hà được tổ chức tại hành tinh \(1\). Triển lãm tiếp theo sẽ được tổ chức tại hành tinh đạt được sau khi dùng máy dịch chuyển đúng \(K\) lần, bắt đầu từ hành tinh \(1\).

Một tên cướp không gian sẽ xâm nhập hệ thống của đúng một hành tinh \(a\) và ghi đè đích đến của máy dịch chuyển tại đó thành hành tinh \(b\). Cảnh sát không biết cụ thể \(a\) và \(b\).

Với mỗi hành tinh \(i\), hãy tính số cặp có thứ tự \((a,b)\) sao cho sau thay đổi này, triển lãm tiếp theo được tổ chức tại hành tinh \(i\).

Dữ liệu vào

• Dòng đầu gồm hai số nguyên \(N,K\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(A_i\), là đích đến hiện tại của máy dịch chuyển tại hành tinh \(i\).

Dữ liệu ra

In \(N\) dòng. Dòng thứ \(i\) chứa số cặp \((a,b)\) khiến hành tinh đạt được sau đúng \(K\) lần dịch chuyển từ hành tinh \(1\) là \(i\).

Lưu ý

• Có thể có \(A_i=i\).
• Có thể chọn \(b=A_a\), tức là thao tác ghi đè không làm thay đổi đích đến. Những cặp như vậy vẫn phải được tính.
• Những cặp có \(a=b\) cũng phải được tính.

Ràng buộc

• \(1 \le N \le 100\,000\).
• \(N \le K \le 10^{18}\).
• \(1 \le A_i \le N\).

Phân nhóm

• Nhóm 1 (10 điểm): \(N \le 100\)
• Nhóm 2 (37 điểm): \(N \le 3\,000\)
• Nhóm 3 (33 điểm): Các giá trị \(A_i\) đôi một khác nhau
• Nhóm 4 (20 điểm): Không có ràng buộc bổ sung

Ví dụ

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