8. Absurdistanské diaľnice

V Absurdistane majú už dlho v pláne postaviť novú sieť diaľnic. Ale viete, ako to chodí: každé štyri roky sú voľby, s ktorými príde nový minister dopravy. Ten vždy najprv preplánuje celú dialničnú sieť a potom už do konca volebného obdobia nič nestihne. Následne príde nový minister a taktiež nanovo prerobí celé plány. Predchádzajúci minister si však rok pred voľbami povedal, že túto tradíciu poruší a diaľnicu stavať naozaj začne. Lenže žiadnu cestu za rok nepostaví, a preto, aby po ňom niečo ostalo, rozhodol sa postaviť aspoň diaľničné križovatky.

Preto zobral svoje plány a náhodne z nich vybral pár miest kde sa do volieb postavili križovatky.

Po ňom však prišiel nový minister. Ten podľa zvyku staré plány zahodil a teraz má pred sebou tažkú úlohu: musí naplánovať celú diaľničnú sieť tak, aby dopĺňala už existujúce križovatky. Keďže chce mať v plánoch poriadok, určil si nasledujúce dva ciele: musí použiť čo najmenej rôznych diaľnic a všetky z nich musia ísť buď v severo-južnom alebo západo-východnom smere. Dokážete aj vy za takýchto podmienok zostrojiť nový plán diaľnic?

Úloha

Na vstupe dostanete zoznam všetkých diaľničných križovatiek postavených predchádzajúcim ministrom.

Vašou úlohou je navrhnúť diaľničnú sieť tak, aby obsahovala všetky tieto križovatky.

Cez každú križovatku musia prechádzať dve diaľnice (keď už je tam ten nadjazd, je to už vybudovaná diaľnica a teda ju nemožno zrušiť), môžu však byť akokoľvek krátke (stačí keď sa diaľnica končí hneď za nadjazdom). Žiadne dve diaľnice sa nemôžu križovať mimo križovatky (to by bolo divné, nie?). Nemôžete postaviť žiadnu novú križovatku, lebo na to nemáte financie.

Formát vstupu

Na prvom riadku vstupu sa nachádza číslo \(n\) – počet križovatiek. Na nasledujúcich \(n\) riadkoch sú vymenované jednotlivé križovatky. Na každom riadku sú súradnice \(1 \le x_i, y_i \le 10^9\): zemepisné súradnice jednotlivých križovatiek.

Formát výstupu

Na výstup vypíšte navrhnutú diaľničnú sieť. V prvom riadku vypíšte číslo \(H\): počet západo-východných diaľnic.

Potom vypíšte \(H\) riadkov. Na každom riadku vypíšte štyri čísla \(1 \le x_i, y_i, x'_i, y'_i \le 10^9\), ktoré reprezentujú západo-východnú diaľnicu. Musí platiť, že \(y_i = y'_i\).

V ďalšom riadku vypíšte číslo \(V\): počet severo-južných diaľnic. Potom vypíšte \(V\) riadkov. V každom riadku vypíšte štyri čísla \(1 \le x_i, y_i, x'_i, y'_i \le 10^9\), ktoré reprezentujú severo-južnú diaľnicu. Musí platiť, že \(x_i = x'_i\).

Hodnotenie

Je 8 sád vstupov. Platia v nich nasledovné obmedzenia:

Príklad:

Input:

4
2 1
2 3
1 2
3 2

Output:

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

Všimnite si, že viacero z diaľníc už nepokračuje mimo križovatku.

V diaľničnej sieti však musia byť, keďže v každej križovatke sa musia križovať diaľnice.