7. Ideálny Žbirkov život

Ako každý vie, Meky Žbirka miluje psíkov. Väčšinou ich necháva voľne vypustených vo svojej záhradke v Slovakistane, ale kvôli veľkému nárastu kriminality a krádeží v krajine sa uchýlil k bezpečnejšej alternatíve. Každého psa Meky priviazal k jednej z dvoch gigantických, kompletne čiernych železných tyčí, ktoré mu trčali v záhrade.

Psom sa tento nápad zo začiatku nepáčil. Časom si na to však až tak zvykli, že sa spolu úplne prestali stýkať psíkovia, ktorí boli priviazaní k rôznym tyčiam. Dokonca si podľa toho aj zmenili farbu srsti – pri jednej tyčí na bielu a pri druhej na čiernu.

Po dlhšej dobe však psov omrzelo naďalej prechádzať okolo tyče, aby sa stretli so svojimi kamarátmi. Vymysleli si teda nový spôsob navštevovania. Pes len strašne silno vyskočí, a keďže je k tyči priviazaný, spraví veľký polkruh vzduchom a dopadne presne na opačné miesto na druhej strane tyče. Asi takto:

Psíkovia sú veľmi spoločenskí, preto boli od začiatku prezieravo rozostavení tak, aby každý z nich mohol týmto pohybom stretnúť na opačnej strane tyče nejakého psíka rovnakej farby.

Teraz dostal Meky úžasný nápad. Odfotí svojich psíkov v záhradke svojím novým čierno-čierným foťákom. Nedošlo mu však, že na takejto fotke sa stratí farba psov a dokonca aj pozícia kompletne čiernych tyčí. Teraz by sa však chcel pocháliť ostatným legendárnym spevákom a ukázať im jeho psov na fotke v plnej kráse aj s tyčami, ku ktorím sú priviazaní. Keďže Meky je spevák a nebude sa zaneprázdňovať takými trápnymi úlohami, prischla úloha vám.

Úloha

Psíkov vieme interpretovať ako body v rovine. Z Mekyho fotky vieme zistiť pozície jednotlivých psov, avšak nie pozíciu tyčí, ku ktorým sú priviazaní. Vieme, že pes je buď čierny alebo biely a všetci psíkovia jednej farby sú spolu priviazaní k jednej tyči, ktorá je taktiež bodom v rovine. Zároveň vieme, že pre každého psa existuje na opačnej strane tyče (tej, ku ktorej je priviazaný) pes rovnakej farby. Tyč sa môže nachádzať na pozícií psa. V takom prípade, ak je k nej daný pes priviazaný, je sám sebe na opačnej strane tyče.

Pre zadané pozície psov určite, či existujú také dve tyče a rozdelenie psov do farieb, ktoré spĺňajú podmienky uvedené vyššie.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 300\)) udávajúce počet psov na fotke.

Na \(i\)-tom z nasledujúcich \(n\) riadkov sú \(2\) celé čísla \(x_i, y_i\) \((|x_i|,|y_i|\leq 10^9)\) - \(x\) a \(y\) súradnica \(i\)-teho psa. Žiadna z dvojíc sa na vstupe nevyskytne viac krát - psy sú na rôznych miestach.

Formát výstupu

V prípade, že neexistujú dve tyče a rozdelenia psov do farieb, ktoré spĺňajú podmienky zadania, vypíšte na jediný riadok výstupu zbirka dozbirkoval.

V opačnom prípade vypíšte \(3\) riadky.

• Na prvom riadku zbirka je kral.
• Na druhom riadku štyri čísla oddelené medzerami \(tx_0\) \(ty_0\) \(tx_1\) \(ty_1\) - súradnice prvej a druhej tyče v poradí (\(x\) a \(y\)).
• Na treťom riadku pre každého psa vypíšte bez medzier jedno číslo, buď \(0\), ak má byť priviazaný k tyči \(0\) alebo \(1\) ak má byť priviazaný k tyči \(1\).

Ak existuje viac riešení, môžete vypísať ľubovoľné z nich. Súradnice tyčí vypíšte s dostatočnou presnosťou za desatinnou čiarkou.

Hodnotenie

Príklady

Input:

6
1 1
2 2
4 4
5 5
10 -5
10 -100

Output:

zbirka je kral
3 3 10 -52.5
000011

Input:

5
1 1
5 5
10 -5
10 -100
100000 10000

Output:

zbirka dozbirkoval

Jedna tyč musí byť medzi 1. a 2. psom, jedna medzi 3. a 4. a pre 5. už nič nezostane.