← 返回题目列表

Codeforces · 778/B

B. 按位公式

中文机器翻译题面 查看原题

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。