Problem D
Bank Closing

Bankinn sem þú vinnur við var að drukkna í viðskiptavinum í allan dag og ekki hefur tekist að halda röðum í skefjum. Því eru nú heilmargir viðskiptavinir sem standa og bíða. Eins og stendur standa $n$ manns í $k$ röðum sem leiða að $k$ afgreiðsluborðum.

Hins vegar er komið að hádegispásu, og á meðan henni stendur verður bara eitt afgreiðsluborð opið. Til að koma í veg fyrir reiða viðskiptavinu og ringulreið þarf að sameina raðirnar með skynsamlegum hætti. Þú getur spurt fólk hvenær það mætti í bankann og það mun auðvitað svara því heiðarlega.

Nýja röðin ætti að vera í vaxandi röð eftir hvenær fólk mætti, bara eins og raðirnar eru nú. Getur þú komið þessu í verk?

Þú veist hvenær allir sem eru fremst í sinni röð mættu, svo þú hefur aðeins eina aðgerð í boði. Þú getur valið einhvern til að fara í nýju röðina, og færð svo að vita hvenær manneskjan sem vara fyrir aftan þá manneskju mætti.

Ef það eru jafntefli má raða þeim innbyrðis hvernig sem er.

Gagnvirkni

Þetta er gagnvirkt verkefni. Lausnin þín verður keyrð á móti gagnvirkum dómara sem les úttakið frá lausninni þinni og skrifar í inntakið á lausninni þinni. Þessi gagnvirkni fylgir ákveðnum reglum:

Fyrst les forrit þitt línu sem inniheldur tvær heiltölur aðskilin með bili, $n$ og $k$. Gildi $n$ táknar fjölda viðskiptavina og $k$ fjölda biðraða. Þessi gildi uppfylla $n \leq 100\, 000$ og $2 \leq k \leq n$.

Næst les forrit þitt $k$ heiltölur $t_1, t_2, \dots , t_k$ á einni línu aðskilin með bili. Gildið $t_i$ táknar hversu mörgum sekúndum eftir opnun manneskjan sem er fremst í röð $i$ mætti. Þessi gildi eru öll ekki neikvæð og mest $10^9$.

Svo meðan það eru viðskiptavinir eftir til að setja í nýju biðröðina er eftirfarandi endurtekið.

Forrit þitt á að prenta vísi biðraðarinnar sem þú vilt taka manneskju úr til að setja í nýju biðröðina. Fyrsta röðin er með vísi $1$ og sú síðasta með vísi $k$. Svo á forrit þitt að lesa eina línu. Ef biðröðin sem þú tókst úr er nú tóm mun þessi lína innihalda strenginn DONE. Annars mun þessi lína innihalda eina heiltölu $T$, tímann eftir opnun sem manneskjan fyrir aftan mætti. Þetta gildi verður ávallt ekki neikvætt, mest $10^9$ og að minnsta kosti jafn stór og tíminn fyrir manneskjuna á undan, ef einhver var á undan.

Þegar allir eru komnir í nýju biðröðina á forrit þitt að prenta DONE og síðan ljúka keyrslu.

Vertu viss um að gera flush eftir hverja aðgerð, t.d., með

• print(..., flush=True) í Python,

• cout << ... << endl; í C++,

• System.out.flush(); í Java.

7 3
5 2 3

2

6

3

3

3

5

1

DONE

3

DONE

2

20

2

DONE

DONE