4317: Bitwise Formula

内存限制:256 MB 时间限制:2 S
题面:传统 评测方式:文本比较 上传者:
提交:4 通过:4

题目描述

Bob 最近阅读了关于计算机中位操作的内容:AND、OR 和 XOR。他研究了这些操作的属性,并发明了一种新游戏。
最初,Bob 选择了一个整数 ( m ),这是游戏的位深度,意味着游戏中的所有数字都将由 ( m ) 位组成。然后,他让 Peter 选择一个 ( m ) 位的数字。之后,Bob 计算 ( n ) 个变量的值。每个变量要么被分配一个常数 ( m ) 位数字,要么是位操作的结果。操作数可以是之前定义的变量,也可以是 Peter 选择的数字。之后,Peter 的得分等于所有变量值的总和。
Bob 想知道 Peter 需要选择什么数字才能得到最小可能的得分,以及得到最大可能的得分。对于这两种情况,如果有多种方式可以获得相同的得分,找出 Peter 可以选择的最小数字。

输入格式

第一行包含两个整数n和m,分别是变量数和位深(1≤n≤5000;1≤≤1000)。
下面n行包含变量的描述。每一行只描述一个变量。描述格式如下:新变量名,空格,符号":=",空格,后面跟着其中之一:
正好是m位的二进制数。
第一个操作数,空格,位操作("AND", "OR"或"XOR"),空格,第二个操作数。每个操作数要么是前面定义的变量名,要么是符号'?,表示彼得选择的数字。
变量名是由小写拉丁字母组成的字符串,长度不超过10。所有变量名都是不同的。

输出格式

在第一行中输出Peter应该选择的最小值,使所有变量值的和尽可能小;在第二行中输出Peter应该选择的最小值,使所有变量值的和尽可能大。这两个数字都应该打印为m位二进制数。

输入样例 复制

3 3
a := 101
b := 011
c := ? XOR b

输出样例 复制

011
100

数据范围与提示

在第一个示例中,如果 Peter 选择了数字 0112,那么 a = 1012,b = 0112,c = 0002,它们的值的总和是 8。如果他选择了数字 1002,那么 a = 1012,b = 0112,c = 1112,它们的值的总和是 15。
在第二个测试中,变量 a、bb、cx、d 和 e 的最小和最大总和都是 2,这个总和不依赖于 Peter 选择的数字,因此 Peter 能选择的最小值是 0。