给定一个由三个变量组成的布尔函数,该函数由其真值表定义。您需要找到一个等于该函数的最小长度的表达式。该表达式可能包括:
- AND 运算('&',ASCII 代码 38)
- 运算 OR('|',ASCII 代码 124)
- NOT 运算('!',ASCII 代码 33)
- 变量 x、y 和 z(ASCII 代码 120-122)
- 括号('(',ASCII 代码 40,和 ')',ASCII 代码 41)
如果存在多个最小长度的表达式,您应该找到按字典顺序最小的一个。
操作具有标准优先级。 NOT 具有最高优先级,然后是 AND,OR 具有最低优先级。表达式应满足以下语法:
E ::= E '|' T |时间
T ::= T '&' F | F
F ::= '!' F | '('E')'| 'x' | 'y'| 'z'
输入
第一行包含一个整数 n — 输入中函数的数量 (1 ≤ n ≤ 10 000)。
接下来的n行是函数的描述,其中第i行包含一个长度为8的字符串,由数字0和1组成——第i个函数的真值表。位置 j (0 ≤ j < 8) 上的数字等于 $$x = \left\lfloor \frac{2}{4} \right\rfloor$$、$$y = \left\lfloor \frac{i}{2} \right\rfloor \bmod 2$$ 和 $$z = j \bmod 2$$ 情况下的函数值。
输出
你应该输出n行,第i行应该包含等于第i个函数的最小长度的表达式。如果有多个这样的表达式,则输出其中按字典顺序最小的一个。表达式应该满足给定的语法并且不应包含空格。
示例
输入 #1
4 00110011 00000111 11110000 00011111
输出 #1
y (y|z)&x !x x|y&z
注意
第二个函数的真值表: