Logic

Mircea cel Tânăr trebuie să îmbunătăţească permanent performanţele calculatoarelor pe care le are în gestiune. Se întâmplă câteodată, ca unele componente noi pe care le foloseşte să nu fie compatibile cu vechile calculatoare. Din acest motiv funcţionarea calculatoarelor „îmbunătăţite” poate să nu fie corectă. Pentru a verifica corectitudinea funcţionării acestor calculatoare, Mircea îşi propune să le testeze cu ajutorul unui program care verifică echivalenţa unor expresii logice.

Cerinţă

Scrieţi un program care determină dacă două expresii logice sunt echivalente sau nu. Fiecare expresie este formată din:

• variabile, cele $26$ de litere mici ale alfabetului englez, de la ’a’ – ’z’;
• operatori binari |, &, ^ (SAU, ŞI respectiv SAU EXCLUSIV);
• operatorul unar ~ (NEGAŢIE);
• paranteze rotunde.

Expresiile vor fi evaluate respectând regulile de priorităţi ale operatorilor şi parantezelor pentru evaluarea expresiilor logice în care intervin ca operanzi biţii $0$ şi $1$. Priorităţile în ordine descrescătoare sunt: parantezele rotunde (, ), operatorul unar ~, operatorii binari în ordine descrescătoare &, ^, |.
Două expresii sunt echivalente dacă:

• conţin acelaşi set de variabile indiferent de numărul de apariţii a variabilei în expresie;
• pentru orice set de date de intrare pentru variabile (valori $0$, $1$) rezultatul obţinut este acelaşi.

Date de intrare

Fişierul de intrare logic.in conţine pe primul rând un număr natural $n$, ce reprezintă numărul testelor ce se vor evalua. Fiecare test reprezintă evaluarea a două expresii. Pe următoarele $2 \cdot n$ linii sunt şiruri de caractere ce constituie expresiile. Acestea sunt scrise pe câte o linie fiecare.

Date de ieșire

Fişierul de ieşire logic.out va conţine $n$ linii, pe fiecare linie $k$ fiind mesajul „egale” sau „diferite” în funcţie de rezultatul evaluării expresiilor de pe liniile $2 \cdot k$ şi respectiv $2 \cdot k + 1$ din fişierul de intrare.

Restricții și precizări

• $0 < n \leq 50$;
• $n$ reprezintă numărul de perechi de expresii ce trebuie evaluate;
• O expresie conţine cel mult $100$ de operaţii şi maxim $10$ variabile;
• O expresie poate avea cel mult $255$ caractere. Spaţiul nu este separator în interiorul unei expresii;
• Numele unei variabile este un singur caracter, literă mică a alfabetului englez;
• Expresiile date sunt corecte.

Exemplu

logic.in

4
a&(c|~c)
a
~(a|b|c|d)
~a&~b&~c&~d
z&b
a&b
a|b
(a|~a)&(a|~a)&(a|~a)&(a|b)

logic.out

diferite
egale
diferite
egale

Explicație

Pentru ultimul set de expresii tabelul este:

unde E=(a|~a)&(a|~a)&(a|~a)&(a|b)