Bob 最近阅读了计算机中使用的按位运算:AND、OR 和 XOR。他研究了它们的特性并发明了一种新游戏。
最初,Bob 选择整数 m,即游戏的位深度,这意味着游戏中的所有数字将由 m 位组成。然后他要求 Peter 选择一些 m 位数字。之后,Bob 计算 n 个变量的值。每个变量被分配一个常数 m 位数字或按位运算的结果。该运算的操作数可以是之前定义的变量,也可以是 Peter 选择的数字。之后,Peter 的得分等于所有变量值的总和。
Bob 想知道 Peter 需要选择什么数字才能获得可能的最低分数,以及他需要选择什么数字才能获得可能的最大分数。在这两种情况下,如果有多种方法可以获得相同的分数,请找到他可以选择的最小数字。
输入
第一行包含两个整数 n 和 m,分别是变量数量和位深度(1 ≤ n ≤ 5000;1 ≤ m ≤ 1000)。
以下 n 行包含变量的描述。每一行准确描述一个变量。描述具有以下格式:新变量的名称、空格、符号“:=”、空格,后跟以下之一:
1. 恰好 m 位的二进制数。
2. 第一个操作数,空格,按位运算(“AND”、“OR”或“XOR”),空格,第二个操作数。每个操作数要么是之前定义的变量名,要么是符号“?”,表示Peter选择的数字。
变量名称是由小写拉丁字母组成的字符串,长度最多为10。所有变量名称都不同。
输出
在第一行中输出 Peter 应选择的最小数字,以使所有变量值的总和尽可能最小,在第二行中输出 Peter 应选择的最小数字,以使所有变量值的总和尽可能最大。两个数字都应打印为 m 位二进制数。
示例
输入 #1
3 3 a := 101 b := 011 c := ? XOR b
输出 #1
011 100
输入 #2
5 1 a := 1 bb := 0 cx := ? OR a d := ? XOR ? e := d AND bb
输出 #2
0 0
注意
在第一个样本中,如果 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。