---------------------------------- 
| PROBLEMA 16: Insula Logicii      |    
| PUNCTAJ: 55 Dexteri              |  
| DEADLINE: Luni, 3 Mai            | 
| TIMP DE IMPLEMENTARE: 60 minute  | 
| TIMP DE EXECUTIE: 0.1 sec./test  | 
 ----------------------------------

   Aceasta problema s-a dat la un concurs ACM si am intalnit-o la 
pregatirea pentru ACM faza europeana. Cu toate ca unii dintre voi
(destul de putini) au facut-o la palat cu Catalin Francu, eu totusi
o propun spre rezolvare, nu de alta dar la lot la Medias am dat o
problema de la ACM foarte putin modificata pe care unii (doar de
Batog am auzit) o vazusera acum vr-un an, dar cu toate astea au luat
0 puncte. 

 vali

Insula Logicii

    Insula Logicii are trei tipuri de locuitori: fiinte divine, 
care spun intotdeauna adevarul, fiinte malefice, care mint
intotdeauna, si oameni, care spun adevarul ziua si mint noaptea.
Fiecare locuitor al insulei poate recunoaste tipul oricarui alt
locuitor. 
    Un sociolog vrea sa viziteze insula. Deoarece el nu poate
distinge cele trei tipuri de locuitori doar dupa aspect, el iti 
cere un analizator care sa deduca fapte din conversatiile cu
locuitorii. Faptele care il intereseaz sunt daca este zi sau noapte
si de ce tip sunt interlocutorii sai.
    Intrarea se face din fisierul logic.in care contine o 
conversatie. Fiecare linie a fisierului contine cate o afirmatie
facuta de un locuitor. Toate liniile incep cu numele
interlocutorului (care este o litera mare A,B,C,D sau E) urmat de
":" si apoi o afirmatie de forma: 
  * Eu [nu] mint.
  * Eu [nu] sunt {divin | om | malefic}.
  * X [nu] minte.
  * X [nu] este {divin | om | malefic}.
  * Este {zi | noapte}.

    Cuvintele care sunt cuprinse intre paranteze patrate pot aparea
sau nu in afirmatie. Dintre cuvintele cuprinse intre acolade, apare
exact un cuvant in afirmatie. O conversatie poate avea cel mult 50
afirmatii.

    Iesirea se face in fisierul logic.out in care se va scrie tot 
ceea ce se poate deduce in urmatoarea forma:
  * X este {divin | malefic | om}.
  * Este {zi | noapte}.
    X se inlocuieste cu numele interlocutorului. Faptele trebuie
date in ordine alfabetica, sortate dupa numele interlocutorilor, 
iar apoi se spune daca e zi sau noapte.  Daca nu se poate deduce
nimic se va tipari "Nu se poate deduce nimic.", iar daca conversatia
nu respecta regulile de mai sus se va tipari "Imposibil.".

Restrictii: 
  * Timpul maxim de rulare pentru fiecare test este de 0.1
    secunde.  
  * Problema va fi testata pe 20 de teste.  
  * Datele de intrare sunt corecte.

Exemple:

Exemplul 1:

logic.in 
A: Eu sunt divin. 

logic.out 
Nu se poate deduce nimic.


Exemplul 2: 

logic.in  
A: Eu mint.  

logic.out 
Imposibil.


Exemplul 3:

logic.in  
A: Eu sunt malefic.  

logic.out
A este om. 
Este noapte.  

Exemplul 4: 
logic.in 
A: B este om.  
B: A este malefic. 
A: B este malefic 

logic.out
A este malefic. 
B este divin.


    Tipuri de rationament:
    Pentru a face lucrurile mai clare va voi explica rationamentul
in exemplul trei, cand A spune "Eu sunt malefic.". Ce se poate
deduce din asta ? E evident ca A nu poate fi divin, pentru ca ar
minti, similar nu poate fi malefic, pentru ca ar spune adevarul.
Asadar A trebuie sa fie om, si mai mult, deoarece el minte, este
noapte. In exemplul patru, este evident ca A minte deoarece cele
doua afirmatii ale lui sunt contradictorii. Deci B nu poate fi nici
om, nici malefic, deci el este divin. B spune intotdeauna adevarul,
deci A trebuie sa fie malefic.