D. Рудольф и логическая схема
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Полгода Рудольф размышлял над концепцией логического устройства, которое поможет ему узнать ответ на Главный Вопрос Жизни, Вселенной и Всего Такого. Похоже, что ему наконец удалось учесть все-все нюансы, и он составил самую настоящую логическую схему!

При составлении логической схемы Рудольф руководствовался следующими правилами:

  • Схема составляется на прямоугольном листе, разделённом на квадратные ячейки. В описании схемы каждой ячейке соответствует один символ;
  • Символ $$$\texttt{.}$$$ обозначает пустую ячейку;
  • Символ $$$\texttt{?}$$$ обозначает единственный выход логической схемы;
  • Символы $$$\texttt{1}$$$ и $$$\texttt{0}$$$ обозначают константы ИСТИНА и ЛОЖЬ соответственно;
  • Символы $$$\texttt{!}$$$, $$$\texttt{&}$$$ и $$$\texttt{|}$$$ обозначают логические элементы НЕ, И и ИЛИ соответственно;
  • Каждый символ, обозначающий выход схемы, константу или логический элемент, окружён рамкой из 8 символов $$$\texttt{#}$$$. Различные рамки не пересекаются и не касаются друг друга;
  • Символы $$$\texttt{+}$$$ обозначают соединения между выходом, константами и логическими элементами. Каждое соединение представляет собой прямую или ломаную, продолжающуюся по клеткам, имеющим общие стороны. Начало и конец соединения имеют общие стороны с рамками. Соединения не содержат самопересечений, различные соединения не пересекаются и не касаются друг друга;
  • Рамки выхода схемы и констант имеют 1 примыкающее соединение, рамки элементов НЕ — 2 примыкающих соединения, рамки элементов И и ИЛИ — 3 примыкающих соединения;
  • Соединения различных объектов на схеме образуют связный неориентированный ациклический граф.

Теперь Рудольфу предстоит выяснить, какое логическое значение окажется на выходе устройства, если его собрать по схеме и запустить. Помогите ему найти ответ на этот вопрос.

Входные данные

Ввод содержит 3 или более строк, описывающих логическую схему.

Описание схемы удовлетворяет правилам, описанным выше. Общее количество символов в описании схемы не превосходит $$$10^6$$$.

Выходные данные

Выведите одно целое число — результат выполнения логической схемы.

Примеры
Входные данные
............................................................
............................................................
............###.............................................
............#1#.............................................
............###.............................................
.............+..............................................
.............+..............................................
.............+..............................................
.............+..............................................
.............+..............................................
...###.......+................###...........###.............
...#0#.......+.......###......#1#...........#1#.............
...###.......+.......#1#......###...........###.............
....+........+.......###.......+.............+..............
....+........+........+........+.............+..............
....+........+........+........+.............+..............
....+........+........+........+.............+..............
....+...###..+........+........+.......###...+..............
....++++#&#+++........+........++++++++#|#++++..............
........###...........+................###..................
.........+............+.................+...................
.........+............+.................+...................
.........+............+.................+...................
.........+............+.................+...................
.........+..###.......+.................+...................
.........+++#&#++++++++.................+...................
............###.........................+...................
.............+..........................+...................
.............+..........................+...................
.............+..........................+...................
.............+..........................+...................
.............+............###...........+...................
.............+++++++++++++#|#++++++++++++...................
..........................###...............................
...........................+................................
...........................+................................
...........................+................................
...........................+................................
..........................###...............................
..........................#?#...............................
..........................###...............................
............................................................
............................................................
............................................................
............................................................
Выходные данные
1
Входные данные
..................................................
..................................................
..................................................
..................................................
.....................###..........................
.....................#?#..........................
.....................###..........................
......................+...........................
......................+...........................
......................+...........................
......................+...........................
.....................###..........................
.........++++++++++++#&#++++++++..................
.........+...........###.......+..................
.........+.....................+..................
.........+.....................+..................
.........+.....................+..................
.........+.....................+..................
........###...................###.................
....++++#|#+++........++++++++#|#++++.............
....+...###..+........+.......###...+.............
....+........+........+.............+.............
....+........+........+.............+.............
....+........+........+.............+.............
....+........+........+.............+.............
...###......###......###...........###............
...#1#......#1#......#1#...........#1#............
...###......###......###...........###............
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
Выходные данные
1