Коля купил новую материнскую плату для своего компьютера, но ему кажется, что она работает некорректно. Возможно неправильно выставлены переключатели на ее разъеме, которые могут находиться в двух состояниях — включен или выключен. Коля хочет узнать текущее состояние переключателей.
К несчастью, переключатели не являются доступными. Но Коля нашел сокет, каждый пин которого соединен с одним из переключателей через некоторую схему. Коля нашел эту схему в Интернете. Он обозначил переключатели маленькими латинскими буквами, а пины сокета — большими буквами. После этого он выписал логическую формулу для каждого пина. Согласно этой формуле включенный переключатель представляется значением true, а выключенный —false.
Коля использует в формуле следующие обозначения (операции перечислены от высшего приоритета к нисшему):
- Обозначение пина — буква от ‘A’ до ‘K’ ;
- Скобки обозначают, что если E >— это формула, то (E) — тоже формула;
- Отрицание — ~E— это формула для любой формулы E;
- Конъюнкция — E1 & E2 &…&En;
- Дизъюнкция — E1| E2| … | En;
- Импликация Е1 => E2 =>… => En. Импликации выполняются справа налево: Е1 => E2 => E3 означат Е1 => (E2 => E3);
- Эквивалентность — Е1 <=> E2 <=> … <=> En. Такое выражение вычисляется так: (Е1 <=> E2) &(Е2<=> E3) & … &(En-1 <=> En)..
Коля может построить новую схему, соответствующую любой формуле. Переменными в этой формуле будут состояния пинов сокета. Для начала он хочет построить схему, в которой входными значениями будут состояния всех пинов сокета, а в качестве выхода мы получим значение единственного переключателя, который при любых входных значениях будет находится в состоянии включено. Напишите программу, которая поможет Коле написать соответствующую формулу.
Входные данные
Первая строка входных данных содержит единственное целое число n — количество пинов у сокета (1 < n < 10). Следующие n строк содержат описания каждого пина. Одно описание состоит из обозначения пина и соответствующей формулы, отделенной от обозначения символами ‘:=’. Пин обозначен заглавной латинской буквой. Его формула расположена в одной строке и состоит из элементов ‘a’..‘k’, ‘(’, ‘)’, ‘~’, ‘&’, ‘ |’, ‘=>’ и ‘<=>’. Элементы формулы могут быть отделены друг от друга произвольным числом пробелов. Описание каждого пина содержит не более 1000 символов.
Выходные данные
Если требуемая схема существует, то выведите в первой строке Yes и No в противном случае.
В первом случае в следующей строке выведите формулу для переключателя, которая всегда истинна. Имя каждого пина должно входить в нее по крайней мере один раз. Имен переключателей она содержать не должна. Длина формулы не должна превосходить 1000 символов.