K. Логика булевых ключей и замков
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Карен и ее друзья играют в музыкальной группе в гараже Карен. У нее сложные мысли о том, какие подмножества группы должны иметь доступ в гараж. Она разработала булеву формулу $$$F$$$, в которой каждая переменная обозначает присутствие определенного участника группы. Она хочет, чтобы группа людей могла войти в гараж только в том случае, если $$$F$$$ истинно.

Вам предлагается создать систему проводов и замков, которая будет удовлетворять формуле $$$F$$$. Каждый участник группы получит ключ, который открывает все замки, обозначенные его буквой.

Например, предположим, что $$$F = a \lor (b \land c)$$$, и участники группы $$$a$$$ и $$$b$$$ присутствуют. Тогда они должны иметь возможность войти в гараж со своими ключами, потому что $$$true \lor (true \land false) = true$$$.

Участник группы не обязан использовать свой ключ для открытия всех возможных замков. Например, предположим, что $$$F = a \oplus b$$$. Тогда участник группы $$$a$$$ в одиночку должен иметь возможность войти в гараж, потому что $$$true \oplus false = true$$$. Но если и $$$a$$$, и $$$b$$$ приходят в гараж, они могут просто игнорировать ключ $$$b$$$ и открыть гараж, используя ключ $$$a$$$. Однако $$$true \oplus true = false$$$, поэтому эта формула $$$F$$$ не может быть удовлетворена.

Система должна быть прямоугольной сеткой размером не более $$$50 \times 50$$$, содержащей горизонтальные провода '-', вертикальные провода '|', соединения проводов '+' и замки. В верхней левой и верхней правой ячейках сетки должны находиться соединения проводов, которые будут присоединены к дверям гаража. Двери гаража остаются закрытыми, пока существует путь между этими двумя соединениями через провода и запертые замки.

Вам нужно разработать такую систему, соответствующую заданной формуле $$$F$$$, или указать, что такая система невозможна.

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

Ввод содержит непустую булеву формулу $$$F$$$.

Формула может содержать буквы a, ..., h, обозначающие присутствие участников группы, операторы «and», «or», «not» и скобки. Длина формулы не превышает 2020 символов. Оператор «not» имеет наивысший приоритет. Оператор «and» имеет более высокий приоритет, чем оператор «or». Вокруг каждого оператора «and», каждого оператора «or» и после каждого оператора «not» должны быть пробелы. Кроме того, не должно быть других пробелов.

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

Если невозможно создать желаемую систему, выведите одну строку «IMPOSSIBLE».

В противном случае выведите прямоугольную сетку символов — систему, соответствующую формуле $$$F$$$. Система может содержать только пробелы, '-', '|', '+' и буквы, соответствующие участникам группы, упомянутым во вводе.

В верхней левой и верхней правой ячейках должны находиться соединения проводов. Ширина сетки должна быть от 2 до 50 включительно, высота сетки должна быть от 1 до 50 включительно.

Символ '-' должен использоваться для провода только в том случае, если он соединяет что-то слева и что-то справа с пустыми ячейками сверху и снизу. Аналогично, символ '|' должен использоваться для провода только в том случае, если он соединяет что-то сверху и что-то снизу с пустыми ячейками слева и справа.

Примеры
Входные данные
a or (b and c)
Выходные данные
+-+ +b-+
| | |  |
+-a-+-c+
Входные данные
(a or f) and ((a and g) or (a and h))
Выходные данные
+a-f+
|   |
+g+h+
a | a
+-+-+
Входные данные
a and not b or not a and b
Выходные данные
IMPOSSIBLE
Входные данные
b or not b
Выходные данные
+ +
Входные данные
d and not d
Выходные данные
+  +---+  +---+--+---+
|  |      |   |  |    
+--+      +---+  |    
|  |      |      |    
+  +------+      +---+