Všetci vieme, že mimozemštania existujú. Dokonca už aj navštívili Zem. Presnejšie povedané, havarovali do nej. Toto miesto je bežne známe ako Area 51. Žiaľ, mimozemštanov sa zmocnilo americké letectvo. Oni si ale zaslúžia byť voľní! Poďme ich zachrániť!
Dvojičky Matty a Robrets pomocou eventu na Facebooku zohnali milióny ochotných ľudí. Ich tímu sa už podarilo preniknúť do tajnej americkej základne, stačí im už len odtiaľ vyniesť mimozemšťanov. Každý človek unesie maximálne dvoch mimozemštanov – jedného v každej ruke. Ale s mimozemšťanom pod pazuchou sa ťažšie beží. Mimozemštanov preto potrebujú rozdeliť tak, aby ten, čo bude niesť najväčšiu záťaž, toho niesol čo najmenej. Preniknutie do základne bolo veľmi náročné, a počítať sa im už nechce. Preto im musíte pomôcť vy!
Úloha
V Area 51 je \(m\) mimozemšťanov. Na to, aby sme ich zachránili, máme \(n\) ľudí. Každý človek unesie maximálne dvoch mimozemšťanov. Každý mimozemšťan má nejakú konkrétnu hmotnosť \(H_i\) udanú v miligramoch.
Mimozemšťanov musíme rozdeliť medzi jednotlivých ľuďí tak, aby maximálna hmotnosť ktorú má niektorý človek niesť, bola najmenšia možná.
Formát vstupu
V prvom riadku vstupu sú čísla \(n\) a \(m\) (\(1\leq m\leq 2n\leq 200\,000\)) udávajúce počet ľudí a mimozemšťanov.
V druhom riadku je \(m\) čísiel \(H_i\) (\(1\leq H_i\leq 1\,000\,000\,000\)) udávajúcich hmotnosti mimozemšťanov v miligramoch.
Formát výstupu
Pre každého z \(n\) ľudí vypíšte jeden riadok obsahujúci dve čísla – hmotnosti mimozemšťanov v jednotlivých rukách. Ak má človek niektorú ruku prázdnu, vypíšte hmotnosť 0.
Môžete vypísať ľubovoľné správne riešenie.
Príklady
Input:
3 4
5 1 6 7Output:
7 0
0 6
1 5Najťažší náklad nesie prvý človek, a to \(7mg\)
Input:
3 6
1 2 2 3 3 4Output:
2 3
4 1
3 2Všetci nesú rovnakú hmotnosť, a to \(5mg\).
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.