“2016? No do ….. bre.” zahundral hračkár Hilbert. Rozlepil oči, utrel si zemiakový šalát tečúci z ucha a dal si rozbehový krémeš na dobré ráno. Sviatky ako majú byť. Treba ale ísť do práce a urobiť koncoročnú uzávierku. Vianoce sú totiž každoročne výdatné na zákazníkov a aj na tržby. Hilbert už presne vie, ako to funguje. Do obchodu príde človek a kúpi prvý darček, ktorý mu je ponúknutý. Človek zaň zaplatí a beží do ďalšieho obchodu. Je prakticky jedno, o aký predmet sa jedná. Dokonca ani nezáleží na cene, pokiaľ nie je príliš vysoká. Všetko závisí od toho, ako málo času ostáva do Vianoc – čím menej času, tým väčšie výčitky svedomia má konkrétny nešťastník, a tým viac je ochotný za darček zaplatiť.
Hilbertovi sa stačí pozrieť na hodinky a hneď vie, koľko peňazí môže zákazník minúť. No a to sa dá úžasne využiť. Stačí vždy nájsť najdrahší darček, ktorý je daný človek ešte ochotný kúpiť a ponúknuť mu ho. Hilbertovo podnikavé srdce teraz kruto zaplakalo. Tento prešibaný plán počas minulého roka ani raz nepoužil… To sa však s novým rokom zmení!
Hilbert by predsa len rád vedel, ako by bol jeho biznis prekvital, ak by túto metódu použil už predošlé Vianoce. Podarilo sa mu zrekonštruovať zoznam ľudí, ktorí prišli do jeho obchodu, no nie je si úplne istý, koľko mohol na každom z nich zarobiť.
Úloha
Na vstupe máte vzostupne usporiadané ceny darčekov v Hilbertovom obchode. Postupne k nemu prichádzajú ľudia. Každý človek má maximálne množstvo peňazí, ktoré je ochotný minúť na darček. Človek, ktorý príde neskôr bude vždy ochotný minúť aspoň toľko ako ten, čo prišiel pred ním. Pre každého človeka vypíšte cenu najdrahšieho darčeka, ktorý si ešte môže dovoliť, a ktorý mu teda Hilbert ponúkne. Po tom, čo si ho zákazník kúpi, ho už Hilbert nemôže ponúkať ďalej.
Formát vstupu
Na prvom riadku sú dve čísla \(n\) a \(m\) (\(1 \leq n \leq 1\,000\,000\), \(1 \leq m \leq 1\,000\,000\)) – počet darčekov, ktoré má Hilbert v obchode a počet zákazníkov, ktorý k nemu prídu.
Na druhom riadku je vzostupne usporiadaná postupnosť \(n\) kladných celých čísel \(c_i\) (\(1\leq c_i \leq 10^9\)) – ceny darčekov v Hilbertovom obchode.
Na treťom riadku je vzostupne usporiadaná postupnosť \(m\) kladných celých čísel \(p_i\) (\(1\leq p_i \leq 10^9\)) – množstvo peňazí, ktoré je ochotný minúť \(i\)-ty zákazník.
V polovici sád navyše platí, že \(1 \leq n \leq 1\,000\) a \(1 \leq m \leq 1\,000\).
Formát výstupu
Pre každého zákazníka vypíšte cenu najdrahšieho darčeka, ktorý mu môže Hilbert ponúknuť. Ak taký nie je, vypíšte \(0\).
Príklad
Input:
8 10
1 2 2 2 5 7 10 20
1 1 2 3 6 6 15 21 21 22
Output:
1 0 2 2 5 2 10 20 7 0
Druhému zákazníkovi nevie Hilbert ponúknuť žiadny darček, lebo jediný predmet s cenou nanajvýš 1 si kúpil prvý zákazník. Takisto si všimnite, že aj keď je deviaty zákazník ochotný za darček zaplatiť až cenu 21, Hilbert mu vie ponúknuť iba predmet s cenou 7, lebo zvyšné rozpredal predošlým zákazníkom.
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.