CF778B Bitwise Formula

Bob 最近对计算机中的位运算（AND、OR 和 XOR）产生了兴趣。他研究了这些运算的特性，并发明了一种新型游戏。 首先，Bob 选择一个整数 $m$，代表游戏的位数限制。这意味着游戏中所有参与的数字都由 $m$ 位构成。接着，他让 Peter 选择一个 $m$ 位的数。然后，Bob 根据这个数计算出 $n$ 个变量的值。每个变量的值要么是一个固定的 $m$ 位常量，要么是通过位运算得到的结果。运算的操作数可以是之前定义的变量，或者是 Peter 选择的那个数。最后，Peter 的得分为所有变量值的总和。 现在，Bob 想知道：Peter 应该选择什么数以得到可能的最低总得分？又该选择什么数以得到可能的最高总得分？如果有多种选择，应该输出 Peter 可以选择的最小那个数。

第一行有两个整数 $n$ 和 $m$，分别代表变量的数量和位数限制（$1 \leq n \leq 5000$；$1 \leq m \leq 1000$）。 接下来的 $n$ 行中，每行描述一个变量。描述格式如下：变量名，空格，符号":="，空格，然后是以下两种形式之一： 1. 一个精确的 $m$ 位二进制数。 2. 一个运算表达式，由第一个操作数，空格，一个位运算符（"AND"、"OR" 或 "XOR"），空格，第二个操作数组成。每个操作数要么是已定义的变量名，要么是符号 "?"，表示 Peter 选择的那个数。 变量名由最多 10 个小写字母组成，且互不相同。

第一行输出 Peter 应选择的数，使得所有变量值的总和最小。第二行输出 Peter 应选择的数，使得所有变量值的总和最大。输出形式为 $m$ 位二进制数。

在第一个示例中，如果 Peter 选择数字 $011_2$，则 $a = 101_2$, $b = 011_2$, $c = 000_2$，变量值的总和为 $8$。如果他选择数字 $100_2$，则 $a = 101_2$, $b = 011_2$, $c = 111_2$，总和为 $15$。 对于第二个测试例，变量 $a$，$bb$，$cx$，$d$ 和 $e$ 的最小及最大总和均为 $2$，而这个总和并不受 Peter 选择的数字影响，因此 Peter 可以选择的最小目标数为 $0$。 **本翻译由 AI 自动生成**