Примонидас патша барлық жердегі ең күшті гладиаторды анықтау үшін турнир ұйымдастырып жатыр. Туған қалаларына абырой мен даңқ әкелу үшін Колизейге барлығы $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