يقيم الملك بريمونيداس بطولة للعثور على أقوى مصارع في جميع الأراضي. في المجموع، شق $N$ مصارعًا طريقهم إلى الكولوسيوم ليعيدوا الشرف والمجد إلى مدنهم. يبدأ كل مصارع بمقدار معين من الحيوية (vitality). تشبه الحيوية نقاط الصحة في كونها تعكس مقدار الضرر الذي يمكن للمصارع تحمله، لكنها تمثل أيضًا مقدار الضرر الذي يمكنه إلحاقه (لأن الضربات القوية تتطلب طاقة).

تتكون البطولة من $K$ جولات. في كل جولة، يرتب الملك المصارعين في صف من الأقل حيوية متبقية إلى الأكثر حيوية متبقية، مع كسر التعادل عشوائيًا. يؤمن الملك بريمونيداس بأن القوة الحقيقية للمصارع تكمن في قدرته على تحمل الضربات، لذلك يأمر المصارع الأول (صاحب أقل حيوية متبقية) بتوجيه أقوى ضربة لديه إلى المصارع الثاني. تطرح هذه الضربة حيوية المصارع الأول من حيوية المصارع الثاني. بعد أن يتلقى المصارع الثاني الضربة، يوجه أقوى ضربة لديه (باستخدام حيويته الجديدة المنخفضة) إلى المصارع الثالث، وهكذا. تتكرر هذه العملية حتى يوجه المصارع قبل الأخير أقوى ضربة لديه إلى المصارع الأخير (الذي لا يتاح له مهاجمة أي شخص).

لاحظ أنه في العملية المذكورة أعلاه، لا يمكن أن تنخفض حيوية المصارع أبدًا إلى أقل من الصفر. (المصارع الذي تبلغ حيويته صفرًا يوجه ضربة ضعيفة لا تلحق أي ضرر بالمصارع التالي).

اطبع حيوية كل مصارع بعد $K$ جولات من البطولة، بالترتيب من المصارع الأول إلى المصارع الأخير في الصف.

الإدخال

يحتوي السطر الأول من الإدخال على عددين صحيحين مفصولين بمسافة $N$ ($2 \le N \le 10^5$) و $K$ ($1 \le K \le 10^{18}$): عدد المصارعين وعدد الجولات في البطولة.

يحتوي السطر التالي من الإدخال على $N$ من الأعداد الصحيحة المفصولة بمسافات $v_1, v_2, \dots, v_N$ ($0 \le v_i \le 10^{18}$): الحيوية الابتدائية للمصارعين.

الإخراج

اطبع $N$ من الأعداد الصحيحة المفصولة بمسافات: حيوية المصارعين في نهاية الجولة الـ $K$ من البطولة، بالترتيب الذي يقف به المصارعون حاليًا في الصف.

أمثلة

الإدخال 1

6 3
21 28 24 23 1 12

الإخراج 1

1 1 3 6 3 10

الإدخال 2

3 1000
8 2 10

الإخراج 2

0 0 2