Дистанционный практикум по программированию

Одной из классических задач теории вычислений является задача о выполнимости булевых формул — можно ли подобрать такие значения переменных, входящих в формулу, чтобы её значение стало истинным.

Будем записывать формулы, используя:

* имена входных переменных x1, x2, ..., xN;

* логические операции: AND — конъюнкция ("И"), OR — дизъюнкция ("ИЛИ"), ~ (тильда) — инверсия ("НЕ");

* круглые скобки.

Например, формула

x1 AND x2 AND x5

выполнима, поскольку она принимает истинное значение при x1=x2=x5=1. Формула же

(x1 OR x2) AND ~x1 AND ~x2

невыполнима, поскольку её значение равно нулю при любых комбинациях переменных x1 и x2.

Известно, что в общем виде эта задача является NP-полной. Вам предлагается решить её для частного случая, когда формула имеет вид:

(p1 OR p2) AND (p3 OR p4) AND ... AND (pi OR pj)

а в качестве каждого члена p выступает либо некоторая входная переменная xi, либо её отрицание ~xi.

В первой строке входного файла содержится булева формула, записанная в вышеописанном формате. Общее количество переменных N не превышает 100, длина формулы не превышает 10 000 символов. Слова AND, OR отделяются от соседних символов одним пробелом. Других пробелов в строке нет.

Выходной файл должен содержать слово "YES", если формула выполнима, и "NO" в противном случае.

Пример

STDIN	STDOUT
(x1 OR x2) AND (~x1 OR ~x1) AND (~x2 OR ~x2)	NO