Zadanie

Jednorožec

Počet bodov: 75

Jednorožce. Obľúbené zviera malých dievčatiek a škótov. V našom svete majestátne stvorenie, vzácne a zriedkavo zahliadnuté. V tomto magickom svete ich chovajú akoby kozy na mlieko.

Pastier ženie stádo z ohrady na pastvinu. Ale predsa len, dobre by to vyzeralo mať fotku na jednorožcovi. Teda sa ho popýtate, či by vám nedovolil si jedného pohladkať, nebodaj aj vysadnúť a previezť sa.

“Ná čože, šak skús, ale zdrhňú ti jak splašené,” odfrkol pastier. “Tie potvory sú strašne nedoverčivé a rozmaznané, čuješ? A sprosté jak treska, ale keď im poriadne natlačíš do papule, ta možno sa s tebu aj skamarátia. Len sú furt také fiflené. Kukaj hentam, popri chodníku rastú černice. Na tie sú celkom lačné. A čím bližej ku košiaru, tým váčšie černice nájdeš. A každý krík, čuješ, má inakšie kyslé tie černice. A tie potvory jednorožcové, fíha, to sú také fajnovky! Nedajbože aby si im dal menšiu černicu jak už raz zožrali. A ani za svet nevezmú černicu s rovnakou kyslosťou jak predtým. A ešte aj také sú vymýšľavé, že im najlepšie ide pod zub, keď sa tie kyslosti striedajú jak deň a noc. Prvá černica musí byť čo najkyslejšia, druhá zas najsladšia jak med, potom zas tá najkyslejšia čo ostala, no a tak furt dokola. Ta daj im čo najviac tých černíc, a možno ťa neprebodnú tým rožiskom, keď sa budeš fotiť.”

Viete kyslosti všetkých černicových kríkov smerom na pastvinu. Vyberte, ktoré černice dáte jednorožcom tak, že veľkosti budú rásť, že sa zároveň žiadne kyslosti nebudú opakovať, že ich zároveň bude čo najviac a že spomedzi takýchto možností bude prvá čo najkyslejšia, druhá čo najmenej kyslá, tretia čo najviac, štvrtá čo najmenej, …

Vstup a Výstup

Prvý riadok vstupu obsahuje číslo \(J (1 \leq J \leq 100)\), ktoré označuje počet jednorožcov čo budete kŕmiť. Tie jednorožce sú strašne rozmaznané, takže pre ne budete túto úlohu riešiť samostatne a úplne nezávisle.

Pre každého jednorožca nasledujú dva riadky. Prvý riadok obsahuje číslo \(n_j (1 \leq n_j \leq 3 \cdot 10^5)\), ktoré označuje počet kríkov, z ktorých môžete kŕmiť tohoto jednorožca. Na druhom riadku nasleduje \(n_j\) čísel \(k_{ji} (\leq k_{ji} \leq n_j)\), označujúce kyslosť černíc.

Pre každého jednorožca vypíšte dva riadky. Na prvý riadok vypíšte jedno číslo \(p_j\), najväčší počet černíc čo spĺňa dané vlastnosti. Na druhý riadok vypíšte \(p_j\) medzerou oddelených čísel, kyslosti černíc, ktoré viete nakŕmiť jednorožcom.

Na konci riadku nedávajte prebytočnú medzeru a nevypisujte zbytočné konce riadkov.

Príklad

Input:

4
1
1
4
2 2 2 2
9
4 3 2 4 3 2 4 3 2
4
4 3 2 4

Output:

1
1
1
2
3
4 2 3
3
4 3 2

Pre tretieho jednorožca vieme natrhať černice s kyslosťami (4, 2, 3). Toto je najlepšia kyslosť aká sa dá poskladať z čísel {2, 3, 4}. Pre štvrtého jednorožca sa však toto nedá dosiahnuť a najviac vieme nazbierať iba 3 černice s kyslosťami (4, 3, 2). Tieto kyslosti sú pre jednorožcov horšie ako tie čo dostal tretí jednorožec.

Input:

10
2
1 2
10
3 2 1 4 10 4 2 3 3 2
2
1 2
10
2 2 5 4 4 10 5 1 10 3
9
9 1 7 4 8 4 5 3 1
3
3 3 3
6
1 6 2 2 6 3
6
1 3 3 6 1 1
10
2 1 2 3 2 3 10 1 3 1
7
2 4 2 5 4 6 7

Output:

2
1 2
5
3 1 10 4 2
2
1 2
6
2 4 10 5 1 3
7
9 1 7 4 8 5 3
1
3
4
1 2 6 3
3
3 6 1
4
3 2 10 1
5
4 2 5 6 7