• محدودیت زمان: ۰.۵ ثانیه
• محدودیت حافظه: ۱۲۸ مگابایت

شیرین عسل فهمید که یار نامه‌اش را کامل نخوانده است و تصمیم گرفت برود سراغ یار!!

یار که خیلی ترسیده است می‌خواهد هر چه زودتر از خانه اش بیرون برود.

خانه‌ی یار $n$ اتاق دارد که هر اتاق یک در خروجی و یک عدد از بین $0$ تا $k - 1$ دارد که درِ خروجی هر اتاق به جز اتاق $n$ام به اتاق بعدی باز می‌شود و در اتاق $n$ام به بیرون خانه باز می‌شود و در ثانیه‌ی t در خروجی اتاق‌هایی باز است که عدد آن ها برابر باقی‌مانده‌ی تقسیم $t$ بر $k$ است.

به ازای هر اتاق به یار بگویید که اگر در ثانیه‌ی $0$ در آن اتاق باشد و به بهترین شکل عمل کند در چه ثانیه‌ای می‌تواند از خانه خارج شود (یار در یک ثانیه هر مسافتی را می‌تواند طی کند).

ورودی

در سطر اول ورودی دو عدد طبیعی $n$ و $k$ با فاصله آمده‌اند که در متن سوال توضیح داده شده اند و در سطر بعد $n$ عدد ($a_1 ... a_n$) که با فاصله از هم جدا شده اند آمده که $a_i$ نمایانگر عدد اتاق $i$ام است.

$$1 \le n , k \le 100\ 000$$ $$0 \le a_i \le k - 1$$

خروجی

خروجی باید شامل $n$ خط باشد که در خط $i$ام جواب به ازای اتاق $i$ام را چاپ کنید.

مثال

ورودی نمونه ۱

6 3
2 1 1 0 1 0 

خروجی نمونه ۱

9
6
6
3
3
0