题目描述

Karen 和朋友们在她的车库里组建了一支乐队。Karen 对“哪些成员组合应该被允许进入车库”有一套复杂的规则。

她写出了一个布尔公式 $F$。公式中的每个变量表示某位乐队成员是否在场。Karen 希望：一组人能够进入车库，当且仅当在这一组人的真假赋值下 $F$ 的值为真。

现在你需要设计一套由导线和锁组成的系统来实现公式 $F$。每位成员会得到一把钥匙，可以打开所有标有自己字母的锁。

例如，若

$$F=a\lor(b\land c),$$

而成员 $a,b$ 在场，则他们应该能够进入，因为

$$\text{true}\lor(\text{true}\land\text{false})=\text{true}.$$

成员并不一定要把自己能开的所有锁都打开。

例如考虑异或函数 $F=a\oplus b$。只有 $a$ 一人在场时，应当可以进入；但如果 $a,b$ 都在场，他们完全可以忽略 $b$ 的钥匙，只按只有 $a$ 时的方式开锁，因此也仍然能够进入。可是此时 $a\oplus b=\text{false}$。所以这种函数无法由本题的系统实现。

你要输出一个不超过 $50\times 50$ 的矩形字符网格。网格可以包含：

• -：水平导线；
• |：竖直导线；
• +：导线连接点；
• 字母：对应成员的锁；
• 空格：空单元格。

网格左上角和右上角的单元格必须都是 +，它们分别连接车库门的两个端点。

只要这两个连接点之间仍存在一条由导线和尚未打开的锁组成的路径，车库门就保持关闭。成员利用手中的钥匙打开一些锁后，如果两个端点之间不再连通，就能够打开车库门并进入。

请构造一个恰好实现布尔公式 $F$ 的系统；如果不存在这样的系统，则输出无解。

输入格式

输入仅包含一行非空布尔公式 $F$。

公式中可能包含：

• 字母 a～h，表示不同乐队成员；
• 运算符 and、or、not；
• 圆括号。

公式长度不超过 $2020$。

运算优先级为：

1. not 最高；
2. and 次之；
3. or 最低。

每个 and 和 or 的两侧恰好各有一个空格；每个 not 后恰好有一个空格；除此之外没有其他空格。

输出格式

如果无法构造满足要求的系统，输出：

IMPOSSIBLE

否则输出一个矩形字符网格。

网格只能包含：

• 空格；
• -；
• |；
• +；
• 输入公式中实际出现过的成员字母。

网格宽度必须满足

$$2\le W\le 50,$$

高度必须满足

$$1\le H\le 50.$$

左上角和右上角必须为导线连接点 +。

字符 - 必须且仅能表示一个纯水平导线单元：它的左侧和右侧都连接到其他部件，而上方和下方为空。

类似地，字符 | 必须且仅能表示一个纯竖直导线单元：它的上方和下方都连接到其他部件，而左侧和右侧为空。

样例 1

a or (b and c)

+-+ +b-+
| | | |
+-a-+-c+

样例 2

(a or f) and ((a and g) or (a and h))

+a-f+
|   |
+g+h+
a | a
+-+-+

样例 3

a and not b or not a and b

IMPOSSIBLE

样例 4

b or not b

+ +

样例 5

d and not d

+  +---+  +---+--+---+
|  |      |   | |    
+--+     +---+ |      
|  |     |     |      
+  +------+    +---+