Một trang trại có ~n~ chú bò, chú bò thứ ~i~ có chiều cao ~h_i~ và đứng tại chuồng thứ ~i~ được đánh số từ trái qua phải. Các chuồng bò được ngăn cách bởi các thanh gỗ, cho phép bò có thể di chuyển sang các chuồng lân cận.

Mỗi chú bò có thể di chuyển qua các chuồng kề nhau. Tuy nhiên, một chú bò chỉ chấp nhận ghé thăm một chuồng nếu chiều cao của chú bò ở chuồng đó thấp hơn, hoặc không cao hơn quá ~k~ đơn vị so với nó. Cụ thể, chú bò tại vị trí ~i~ có thể ghé thăm chuồng ~j~ nếu thỏa mãn: ~h_j \le h_i + k~.

Hãy xác định, với mỗi chú bò ~i~, số lượng chuồng bò mà nó có thể ghé thăm (tính cả chuồng ban đầu nếu phù hợp).

Dữ liệu

Vào từ tệp văn bản NAUGHTY.INP:

• Dòng đầu tiên chứa hai số nguyên ~n, k~ với ~1 \le n \le 10^5~, ~0 \le k \le 10^9~.
• Dòng thứ hai chứa ~n~ số nguyên ~h_1, h_2, \ldots, h_n~.

Kết quả

Ghi ra tệp văn bản NAUGHTY.OUT:

• Gồm ~n~ số nguyên, số thứ ~i~ là số lượng chuồng bò mà chú bò ~i~ có thể ghé thăm.

Ví dụ

NAUGHTY.INP

7 3
3 7 4 2 5 6 10

NAUGHTY.OUT

1 7 6 3 6 6 7

Ràng buộc

• Có ~30\%~ số test ứng với ~30\%~ số điểm của bài có ~n \le 1000~.
• Có ~30\%~ số test ứng với ~30\%~ số điểm của bài có ~h_i~ đã được sắp xếp không giảm.
• Có ~40\%~ số test ứng với ~40\%~ số điểm còn lại của bài có ~n \le 10^5~.