Ivan bé nhỏ thích chơi Yamb và đọc truyện tranh siêu anh hùng Marvel. Siêu anh hùng yêu thích của cậu là Người Nhện, một thiếu niên thân thiện trong khu phố tên là Peter Parker, người đã có được siêu năng lực nhờ một vết cắn của con nhện phóng xạ. Ivan mơ mộng rằng một ngày nào đó cậu sẽ có thể nhảy từ tòa nhà chọc trời này sang tòa nhà chọc trời khác, giống như Người Nhện làm trong truyện tranh. Trong một lần mơ mộng như vậy, cậu đã ngủ thiếp đi.

Trong giấc mơ, cậu không còn tên là Ivan nữa, mà tên là Peter Parkour và, bạn đoán đúng rồi, cậu có thể sử dụng kỹ năng parkour của mình để nhảy giữa các tòa nhà chọc trời. Cậu nhanh chóng nhận ra rằng có đúng ~N~ tòa nhà chọc trời xung quanh mình và bằng cách nào đó cậu biết rằng tòa nhà thứ ~i~ cao ~h_i~ mét. Cậu biết rằng cậu có thể nhảy từ tòa nhà thứ ~i~ sang tòa nhà thứ ~j~ nếu phần dư khi chia ~h_i~ cho ~h_j~ bằng ~K~. Hãy giúp Ivan xác định, đối với mỗi tòa nhà chọc trời, số lượng các tòa nhà chọc trời khác mà cậu có thể nhảy tới.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ ~(1 \leq N \leq 300.000)~ và ~K~ ~(0 \leq K < 10^6)~ từ mô tả bài toán.
• Dòng tiếp theo chứa ~N~ số nguyên ~h_i~ ~(1 \leq h_i \leq 10^6)~ từ mô tả bài toán.

Output

Trong một dòng duy nhất, bạn nên xuất ra ~N~ số nguyên cách nhau bằng dấu cách, sao cho số nguyên thứ ~i~ trong số đó đại diện cho số lượng tòa nhà chọc trời khác mà Peter Parkour có thể nhảy tới nếu cậu nhảy từ tòa nhà thứ ~i~.

Chú ý

• Trong các trường hợp kiểm tra có tổng cộng 14 điểm, sẽ có ~1 \leq N \leq 2.000~.
• Trong các trường hợp kiểm tra có thêm 14 điểm nữa, sẽ có tối đa ~2.000~ tòa nhà chọc trời có chiều cao khác nhau.
• Trong các trường hợp kiểm tra có thêm 14 điểm nữa, sẽ có ~K = 0~.

Sample Input 1

2 1
5 5

Sample Ouput 1

0 0

Sample Input 2

6 3
4 3 12 6 8 2

Sample Ouput 2

0 4 0 0 0 0

Sample Input 3

5 1
1 3 5 7 2

Sample Ouput 3

4 1 1 2 0

Giải thích

Làm rõ ví dụ thứ ba:

• Từ tòa nhà chọc trời đầu tiên cao 1 mét, Peter có thể nhảy sang bất kỳ tòa nhà chọc trời nào khác.
• Từ tòa nhà chọc trời thứ hai cao 3 mét, Peter chỉ có thể nhảy sang tòa nhà chọc trời cao 2 mét.
• Từ tòa nhà chọc trời thứ ba cao 5 mét, Peter chỉ có thể nhảy sang tòa nhà chọc trời cao 2 mét.
• Từ tòa nhà chọc trời thứ tư cao 7 mét, Peter có thể nhảy sang các tòa nhà chọc trời cao 2 mét và 3 mét.
• Từ tòa nhà chọc trời thứ năm cao 2 mét, Peter không thể nhảy sang bất kỳ tòa nhà chọc trời nào khác.