POLSKI SPOJ

Ulubionymi zajęciami Piotrusia była logika, na której mógł się wreszcie poczuć spełniony. Na zajęciach Piotruś usłyszał ciekawy problem dotyczący spełnialności...

Formuła logiczna jest spełnialna wtedy i tylko wtedy, gdy jej zaprzeczenie nie jest tautologią, czyli formuła zawsze prawdziwą (dla dowolnych podstawień wartości logicznych). Napisz program, który rozstrzyga, czy podana na wejściu formuła logiczna jest spełnialna. Przyjmujemy, że pojawiające się na wejściu formuły mają postać

gdzie r <= 100, a każde z wyrażeń x_i należy do zbioru {p₁, p₂, …, p₉₉, ~p₁, ~p₂, …, ~p₉₉}.

Wejście

Na wejście programu podana zostanie pewna liczba formuł logicznych. Formuła (x₁ \/ x₂) /\ (x₃ \/ x₄) /\ … /\ (x_2r-1 \/ x_2r) pojawi się na wejściu w postaci

gdzie s_i = +n, gdy x_i = p_n i s_i = -n, gdy x_i = ~p_n. Dla przykładu formuła (p₅ \/ ~p₃) /\ (~p₂₀ \/ ~p₇₀) pojawi się na wejściu jako napis (+05-03)(-20-70). Poszczególne formuły rozdzielone zostaną znakami nowej linii, tzn. każda linia zawierać będzie dokładnie jedną formułę.

Wyjście

Na wyjściu ma się pojawić ciąg zerojedynkowy, który na i-tej pozycji ma zawierać binarną odpowiedź na to, czy i-ta pobrana z wejścia formuła jest spełnialna (0 - nie jest, 1 - jest).

Przykład

Wejście:

(+01-02)(+01+02)(-01+02)(-01-02)
(+05-03)(-20-70)
(+05+05)(+06-06)(+10-11)

Wyjście:

011