- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
علی مدیر یک پروژه پلسازی است که به پایانش نزدیک شده است. در این پروژه ابتدا \(n\) پایه بتنی بر روی زمین ساخته شده است، به طوری که پایهی \(i\)ام در مکان \(x_i\) قرار دارد. برای تکمیل پروژه باید مسیر بین پایهی اول (\(x_1\)) و پایهی آخر (\(x_n\)) با تعدادی تختهچوبی به طول \(T\) به هم متصل شوند. طبق قوانین پلسازی، زیر هر تختهچوب باید حداقل \(k\) پایهی بتنی وجود داشته باشد، تا تختهچوب، سفت در جای خود قرار بگیرد. علی میخواهد بداند به ازای تمام \(k\)های بین \(1\) و \(n\) در صورتی که میتوان پل را ساخت، به حداقل چند تختهچوب نیاز دارد.
در تصویر بالا جواب مسئله برای \(k=2\) برای تست اول نشان داده شده است.
توجه کنید عرض ستونها را صفر در نظر میگیریم. فرض کنید یک تختهچوب یک بازهی بسته مثل \([x, x + T]\) را متصل میکند و ستونهای شامل این بازه، زیر آن در نظر گرفته میشود. شما باید بازهی \([x_1, x_n]\) را متصل کنید و ممکن است تخته چوبها اشتراک داشته باشند.
ورودی
در خط اول ورودی دو عدد طبیعی \(n\) و \(T\) با فاصله از هم آمده است.
\[1 \le n \le 100 \, 000\] \[1 \le T \le 10^9\]
در خط دوم ورودی \(n\) عدد آمده است که مکان پایههای بتنی پل را نشان میدهد. عدد \(i\)ام آن برابر \(x_i\) است. \[0 \le x_i \le 10^9\]
تضمین میشود که \(x_1 \lt x_2 \lt \dots \lt x_n\,\) باشد.
خروجی
در تنها خط خروجی، \(n\) عدد خروجی دهید که نشاندهندهی جواب مسئله، به ترتیب به ازای \(k\)های \(1\) تا \(n\) باشد و اگر ساختن پل ممکن نبود، بهجای تعداد تختهچوبها -1 چاپ کنید.
ورودی نمونه ۱
4 2
1 2 4 5
خروجی نمونه ۱
2 2 -1 -1
ورودی نمونه ۲
4 10
0 1 2 20
خروجی نمونه ۲
2 -1 -1 -1