Počet bodov:
Program:  20b

Tina rada organizuje párty pre svojich spolužiakov. Zorganizovať dobrú párty však nie je len tak. Medzi jej spolužiakmi panujú rôzne vzťahy. Napríklad Miro teraz strašne letí na Zuzu. Ak Tina pozve na párty Zuzu, určite musí pozvať aj Mira, inak by jej to do smrti vyčítal. No a Zuza sa minule strašne pohádala s Helou, a tak ak Tina pozve jednu z nich, určite nechce pozvať zároveň aj tú druhú. A tak ďalej.

Keď si tak Tina spísala všetky požiadavky koho môže a nemôže pozvať, zistila, že existujú presne tri možnosti, akú množinu spolužiakov na párty pozvať. Zorganizovala preto postupne tri párty – jednu pre každú možnosť.

Tina ti dala pre každú párty zoznam ľudí, ktorí sa jej zúčastnili. Nájdi jednu možnosť toho, ako vyzerajú vzťahy medzi ľuďmi v triede.

Úloha

Ľudí v triede si očíslujeme od \(1\) po \(n\).

Budeme uvažovať len jeden typ podmienok: implikácie. Každá podmienka má teda tvar “ak (niekto je alebo nie je na párty) tak (niekto musí alebo nesmie byť na párty)”. To, že človek \(x\) je/musí byť na párty, v podmienke zapíšeme \(+x\). To, že tam nie je/nesmie byť, zapíšeme \(-x\).

Na vstupe sú dané tri množiny ľudí, ktoré boli na párty. Zostrojte konkrétnu sadu implikácií, pre ktorú bude platiť, že existujú presne tri spôsoby, ako ich všetky naraz splniť, a tieto tri spôsoby zodpovedajú daným trom množinám ľudí.

Formát vstupu

V prvom riadku vstupu je číslo \(n\): počet ľudí v triede. Zvyšok vstupu tvoria tri riadky. V každom riadku je \(n\) núl alebo jednotiek: postupne od človeka \(1\) po človeka \(n\) je tam \(0\) ak na párty nebol, a \(1\) ak na nej bol.

Vstupom môžu byť ľubovoľné tri \(n\)-tice núl a jednotiek. Nie je teda zaručené, že hľadaná sada implikácií musí existovať.

Je päť sád vstupov. Postupne majú maximálnu hodnotu \(n\) rovnú \(3\), \(5\), \(10\), \(20\) a \(50\).

Formát výstupu

Ak neexistuje žiadna sada implikácií s požadovanou vlastnosťou, vypíšte jeden riadok a v ňom číslo \(-1\).

Ak existujú nejaké vyhovujúce sady implikácií, nájdite nejakú dostatočne malú. Presnejšie, sada, ktorú vypíšete, musí mať nanajvýš \(470\) implikácií. Vypíšte ju v nasledovnom formáte: najskôr riadok obsahujúci číslo \(p\) udávajúce počet implikácií, potom \(p\) riadkov a v každom z nich implikácia tvaru “ak [cislo] tak [cislo]”.

(Je zaručené, že ak existuje nejaká sada implikácií, existuje aj dostatočne malá sada.)

Príklady

Input:

3
0 0 0
0 1 0
1 0 0

Output:

ak +1 tak -2
ak +3 tak +1
ak +3 tak +2

Tina má troch kamarátov. Nazvime ich Anka (1), Boris (2) a Cecil (3). Na prvej párty nebol nik z nich. Na druhej bol len Boris. Na tretej bola len Anka. Ako môže vyzerať sada implikácií, pre ktorú sú toto jediné tri možnosti, koho pozvať?

Existuje veľa možností. Tá uvedená v príklade výstupu má nasledujúci význam: Ak Tina pozve Anku, nesmie pozvať Borisa. Ak pozve Cecila, musí pozvať Anku aj Borisa.

Logicky si odvoďme, koho môže Tina pozvať pre túto sadu implikácií. Ak by pozvala Cecila, tak z druhej a tretej implikácie musí pozvať aj zvyšných dvoch, to však spôsobí spor s prvou implikáciou. Preto Cecil má smolu a na žiadnej párty nebude. Do úvahy tiež nepripadá párty, na ktorej sú Anka s Borisom – opäť pre spor s prvou implikáciou. No a ľahko overíme, že už ostali len tie tri možnosti, ktoré boli zadané na vstupe, a že žiadna z nich k sporu nevedie.

Existujú aj iné správne riešenia. Mohli sme napríklad použiť aj implikáciu “ak +3 tak -3”, z ktorej by tiež vyplývalo, že Cecil na žiadnu párty nesmie.

Input:

4
0 0 1 0
1 0 0 0
1 0 1 1

Output:

-1

Neexistuje sada implikácií, pre ktorú by boli prípustné len tieto tri zloženia účastníkov párty a žiadne iné.

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.