המלך פרימונידאס מארגן טורניר כדי למצוא את הגלדיאטור החזק ביותר בכל הארצות. בסך הכול $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