Satisfactibilitat P93741

Statement

Feu un programa que trobi totes les solucions d’un conjunt de $m$ clàusules $c_1, \dots, c_m$ de tres literals en forma normal conjuntiva.

Per exemple, $\{a = \mbox{\em cert}, b = \mbox{\em fals}, c = \mbox{\em cert}, d = \mbox{\em cert}\}$ és una solució possible per a les tres clàusules $a \enspace \mbox{o} \enspace b \enspace \mbox{o} \enspace c, \quad \mbox{no} \enspace a \enspace \mbox{o} \enspace b \enspace \mbox{o} \enspace c, \quad b \enspace \mbox{o} \enspace \mbox{no} \enspace c \enspace \mbox{o} \enspace d.$

Com un altre exemple, $\{a = \mbox{\em cert}, b = \mbox{\em fals}\}$ és una solució possible per a la clàusula $b \enspace \mbox{o} \enspace \mbox{no} \enspace a \enspace \mbox{o} \enspace a.$ Sent rigurosos, aquesta clàusula no té tres literals (de fet és igual a cert, que no en té cap), però en aquest exercici permetem tenir literals repetits dins de la mateixa clàusula.

Entrada

L’entrada consisteix en un natural $1 \le n \le 20$ , seguit d’un natural $m > 0$ , seguit de $c_1, \dots, c_m$ . Els noms de les variables són les $n$ primeres lletres minúscules, totes les quals apareixen a l’entrada com a mínim una vegada. Els literals negats s’indiquen amb un canvi de signe davant de la variable.

Sortida

Escriviu totes les solucions possibles del conjunt de clàusules. Els literals de cada solució han de sortir en ordre alfabètic. Si no hi ha cap solució, escriviu un guió.

Informació sobre el corrector

Podeu escriure les solucions d’aquest exercici en qualsevol ordre.

Public test cases

Input

4
7
a b c
-a -d c
a c c
-c b -b
a -b -c
-b -c -d
-d -d -d

Output

a b c -d
a b -c -d
a -b c -d
a -b -c -d
-a -b c -d

Input

3
5
c c a
a b -c
-a b b
-b -b -b
-c -c -b

Output

Information

Author: Salvador Roura
Language: Catalan
Other languages: English
Official solutions: C++
User solutions: C++