กษัตริย์พริโมนิดัสกำลังจัดการแข่งขันทัวร์นาเมนต์เพื่อค้นหาแกลดดิเอเตอร์ที่แข็งแกร่งที่สุดในแผ่นดิน มีแกลดดิเอเตอร์ทั้งหมด $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