Ivan thích chơi Yamb và đọc truyện siêu anh hùng Marvel. Cậu thích nhất là Spider-man, người hàng xóm tuổi teen thân thiện có được sức mạnh siêu nhiên khi bị nhện nhiễm phóng xạ cắn. Cậu ước rằng một ngày mình thể nhảy từ tòa nhà này sang tòa nhà khác giống như Spider-man. Trong lúc ước mơ, cậu rơi vào giấc ngủ.

Trong giấc mơ của mình tên của cậu không còn là Ivan nữa mà là Peter Parkour và, bạn đoán đúng rồi đấy, cậu ấy có thể nhảy từ tòa nhà này sang tòa nhà khác. Cậu ấy nhanh chóng nhận ra rằng trong khu phố của mình có ~N~ tòa nhà chọc trời và cậu biết tòa nhà thứ ~i~ cao ~h_i~ mét. Cậu có thể nhảy từ tòa nhà ~i~ sang tòa nhà ~j~ nếu phần dư khi thực hiện phép chia ~h_i~ cho ~h_j~ là ~K~.

Hãy giúp Ivan xác định với mỗi tòa nhà ~i~ cậu ấy có thể nhảy sang bao nhiêu tòa nhà khác.

Input

Dòng đầu tiên chứa 2 số nguyên ~N~ ~(1 \leq N \leq 300\:000)~ và ~K~ ~(0 \leq K \leq 10^6)~.

Dòng tiếp theo chứa ~N~ số nguyên ~h_i~ ~(1 \leq h_i \leq 10^6)~.

Output

Một dòng duy nhất gồm ~N~ số nguyên mỗi số cách nhau 1 khoảng trắng. Số thứ ~i~ là số tòa nhà khác nhau cậu ấy có thể nhảy đến nếu bắt đầu ở tòa nhà thứ ~i~.

Sample Input 1

2 1
5 5

Sample Output 1

0 0

Sample Input 2

6 3
4 3 12 6 8 2

Sample Output 2

0 4 0 0 0 0

Sample Input 3

5 1
1 3 5 7 2

Sample Output 3

4 1 1 2 0

Giải thích

Ở ví dụ 3:

• Từ tòa nhà đầu tiên có chiều cao là 1, Peter có thể nhảy đến bất kì tòa nhà nào.
• Từ tòa nhà thứ 2 có chiều cao là 3, Peter chỉ có thể nhảy đến tòa nhà có chiều cao là 2.
• Từ tòa nhà thứ 3 có chiều cao là 5, Peter chỉ có thể nhảy đến tòa nhà có chiều cao là 2.
• Từ tòa nhà thứ 4 có chiều cau là 7, Peter có thể nhảy sang tòa nhà có chiều cao là 2 và 3.
• Từ tòa nhà thứ 5 có chiều cao là 2, Peter không thể nhảy sang bất kì tòa nhà nào khác.

Ràng buộc

• ~2~ test đầu tiên có ~1 \leq N \leq 2000~.
• ~2~ test tiếp theo sẽ có tối đa ~2000~ tòa nhà có chiều cao khác nhau.
• ~2~ test kế tiếp sẽ có ~K = 0~.
• ~4~ test còn lại không giới hạn gì thêm.