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ța

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 &, ^, | (ŞI, SAU EXCLUSIV respectiv SAU);
• 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. Se dau n numere naturale. Calculați suma lor.

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 * 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*k şi respectiv 2*k+1 din fişierul de intrare.

Restricții și precizări

• 0 < n ≤ 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)