Zadanie

Dobrá predpoveď

Počet bodov: 35, časový limit: 300ms

Buj sa rozhodol, že si vyskúša predpovedať počasie. Každý z predchádzajúcich \(n\) dní spravil \(m\) rôznych experimentov alebo pozorovaní, pričom výsledok každého z nich sa dá zosumarizovať ako áno/nie. Ako príklady uvedieme: či vonku svietilo slnko, či bolo oblačno, či bolo vidno mesiac, či boli banány v záhrade zelené, …

Každý z týchto dní si takisto zaznačil, či pršalo. Teraz by chcel vymyslieť logickú formulu, ktorá mu každý deň bude vedieť predpovedať, či bude pršať alebo nie. (Predstavte si niečo takéto: “Pršať bude práve vtedy, keď je oblačno a zároveň nesvieti slnko.”)

Táto formula musí byť samozrejme konzistentná s dátami, ktoré nazbieral. To znamená, že ak ju použije na predpoveď v každom z \(n\) pozorovaných dní, dá nám správnu odpoveď.

Nájdite jednu takú formulu, ak existuje.

Vstup a výstup

Na prvom riadku vstupu sú medzerou oddelené dve kladné celé čísla \(n\) a \(m\): počet dní a počet experimentov. Platí \(n \cdot m \leq 5\,000\). Nasleduje \(n\) riadkov, každý popisuje výsledky experimentov v príslušnom dni a tiež či v ten deň pršalo. Formát \(i\)-teho riadku je nasledovný: \[ k_{i, 1} k_{i, 2} \ldots k_{i, m} = p_i, \] pričom \(k_{i, j}\) je \(0\) (výsledok experimentu \(j\) je “nie”) alebo \(1\) (“áno”), a \(p_i\) je \(0\) (v daný deň nepršalo) alebo \(1\) (pršalo).

Ak neexistuje formula konzistentná s týmito pozorovaniami, vypíšte impossible. V opačnom prípade na výstup vypíšte ľubovoľnú jednu takú boolovskú formulu. Musí mať presne nasledovnú syntax:

• Boolovská formula je term.
• Term je buď:
  • Premenná.
  • Alebo \((t_1 \circ t_2 \circ \ldots \circ t_n)\) pre \(n \geq 1\), kde \(t_1, t_2\) sú termy a \(\circ\) je buď \(||\) (boolovský OR) alebo \(\&\&\) (boolovský AND). Ak \(n > 2\), tak takýto výraz čítame, že je uzátvorkovaný zľava, t.j. \((a\ ||\ b\ \&\&\ c)\) znamená \(((a\ ||\ b)\ \&\&\ c)\).
  • Alebo \(!t\), kde \(t\) je term. Operátor \(!\) zodpovedá boolovskej negácii.
• Premenná je reťazec začínajúci znakom x, za ktorým nasleduje ľubovoľné kladné celé číslo (vzťahujúce sa na výsledok príslušného experimentu). Medzery nemusíte vo formule uvádzať. Vaša formula musí byť dlhá aspoň \(1\) a nanajvýš \(100\,000\) znakov.

Príklad

Input:

5 3
1 0 0 = 0
0 1 1 = 0
0 1 0 = 1
0 0 1 = 1
0 0 0 = 1

Output:

!((x1) || (x2 && x3))

Input:

3 3
1 0 0 = 1
0 1 0 = 1
0 0 1 = 1

Output:

(x1 || x3 || !!x2)

Input:

2 1
0 = 0
0 = 1

Output:

impossible