Bob recently read about bitwise operations used in computers: _AND_, _OR_ and _XOR_. He have studied their properties and invented a new game.
Initially, Bob chooses integer _m_, bit depth of the game, which means that all numbers in the game will consist of _m_ bits. Then he asks Peter to choose some _m_\-bit number. After that, Bob computes the values of _n_ variables. Each variable is assigned either a constant _m_\-bit number or result of bitwise operation. Operands of the operation may be either variables defined before, or the number, chosen by Peter. After that, Peter's score equals to the sum of all variable values.
Bob wants to know, what number Peter needs to choose to get the minimum possible score, and what number he needs to choose to get the maximum possible score. In both cases, if there are several ways to get the same score, find the minimum number, which he can choose.
## Input
The first line contains two integers _n_ and _m_, the number of variables and bit depth, respectively (1 ≤ _n_ ≤ 5000; 1 ≤ _m_ ≤ 1000).
The following _n_ lines contain descriptions of the variables. Each line describes exactly one variable. Description has the following format: name of a new variable, space, sign "_:=_", space, followed by one of:
1. Binary number of exactly _m_ bits.
2. The first operand, space, bitwise operation ("_AND_", "_OR_" or "_XOR_"), space, the second operand. Each operand is either the name of variable defined before or symbol '_?_', indicating the number chosen by Peter.
Variable names are strings consisting of lowercase Latin letters with length at most 10. All variable names are different.
## Output
In the first line output the minimum number that should be chosen by Peter, to make the sum of all variable values minimum possible, in the second line output the minimum number that should be chosen by Peter, to make the sum of all variable values maximum possible. Both numbers should be printed as _m_\-bit binary numbers.
[samples]
## Note
In the first sample if Peter chooses a number 0112, then _a_ = 1012, _b_ = 0112, _c_ = 0002, the sum of their values is 8. If he chooses the number 1002, then _a_ = 1012, _b_ = 0112, _c_ = 1112, the sum of their values is 15.
For the second test, the minimum and maximum sum of variables _a_, _bb_, _cx_, _d_ and _e_ is 2, and this sum doesn't depend on the number chosen by Peter, so the minimum Peter can choose is 0.
Bob 最近学习了计算机中使用的位运算：_AND_、_OR_ 和 _XOR_。他研究了它们的性质，并发明了一个新游戏。
最初，Bob 选择一个整数 #cf_span[m]，作为游戏的位深度，这意味着游戏中的所有数字都由 #cf_span[m] 位组成。然后他要求 Peter 选择一个 #cf_span[m] 位的数字。之后，Bob 计算 #cf_span[n] 个变量的值。每个变量被赋值为一个常数 #cf_span[m] 位数字，或一个位运算的结果。运算的操作数可以是之前定义的变量，也可以是 Peter 选择的数字。之后，Peter 的得分等于所有变量值的和。
Bob 想知道，Peter 应该选择什么数字才能使总得分最小，以及选择什么数字才能使总得分最大。在两种情况下，如果存在多种选择能得到相同的得分，则应找出其中最小的数字。
第一行包含两个整数 #cf_span[n] 和 #cf_span[m]，分别表示变量数量和位深度（#cf_span[1 ≤ n ≤ 5000]；#cf_span[1 ≤ m ≤ 1000]）。
接下来的 #cf_span[n] 行描述了各个变量。每行描述一个变量，格式如下：新变量名，空格，符号 "_:=_"，空格，后接以下之一：
变量名是由最多 10 个小写拉丁字母组成的字符串。所有变量名均不同。
第一行输出使所有变量值之和最小的 Peter 应选择的数字，第二行输出使所有变量值之和最大的 Peter 应选择的数字。两个数字都应以 #cf_span[m] 位二进制数形式输出。
在第一个样例中，如果 Peter 选择数字 #cf_span[0112]，则 #cf_span[a = 1012, b = 0112, c = 0002]，它们的值之和为 #cf_span[8]。如果他选择数字 #cf_span[1002]，则 #cf_span[a = 1012, b = 0112, c = 1112]，它们的值之和为 #cf_span[15]。
对于第二个测试用例，变量 #cf_span[a]、#cf_span[bb]、#cf_span[cx]、#cf_span[d] 和 #cf_span[e] 的最小和最大和均为 2，且该和不依赖于 Peter 选择的数字，因此 Peter 可选择的最小数字是 #cf_span[0]。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[m]，分别表示变量数量和位深度（#cf_span[1 ≤ n ≤ 5000]；#cf_span[1 ≤ m ≤ 1000]）。接下来的 #cf_span[n] 行描述了各个变量。每行描述一个变量，格式如下：新变量名，空格，符号 "_:=_"，空格，后接以下之一：
- 恰好 #cf_span[m] 位的二进制数。
- 第一个操作数，空格，位运算（"_AND_"、"_OR_" 或 "_XOR_"），空格，第二个操作数。
每个操作数要么是之前定义的变量名，要么是符号 '_?_'，表示 Peter 选择的数字。
变量名是由最多 10 个小写拉丁字母组成的字符串。所有变量名均不同。
## Output
第一行输出使所有变量值之和最小的 Peter 应选择的数字，第二行输出使所有变量值之和最大的 Peter 应选择的数字。两个数字都应以 #cf_span[m] 位二进制数形式输出。
[samples]
## Note
在第一个样例中，如果 Peter 选择数字 #cf_span[0112]，则 #cf_span[a = 1012, b = 0112, c = 0002]，它们的值之和为 #cf_span[8]。如果他选择数字 #cf_span[1002]，则 #cf_span[a = 1012, b = 0112, c = 1112]，它们的值之和为 #cf_span[15]。
对于第二个测试用例，变量 #cf_span[a]、#cf_span[bb]、#cf_span[cx]、#cf_span[d] 和 #cf_span[e] 的最小和最大和均为 2，且该和不依赖于 Peter 选择的数字，因此 Peter 可选择的最小数字是 #cf_span[0]。
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ denote the number of variables and bit depth, respectively.
Let $ x \in \{0,1\}^m $ be the $ m $-bit binary number chosen by Peter.
Let $ V = \{v_1, v_2, \dots, v_n\} $ be a sequence of variables, each defined by:
- a name, and
- an expression of the form:
$$
\text{const} \in \{0,1\}^m \quad \text{or} \quad e_1 \odot e_2
$$
where $ \odot \in \{\text{AND}, \text{OR}, \text{XOR}\} $, and each $ e_1, e_2 $ is either a previously defined variable or $ x $.
**Constraints**
1. $ 1 \le n \le 5000 $, $ 1 \le m \le 1000 $
2. All variable names are distinct and consist of at most 10 lowercase Latin letters.
3. Each expression is well-formed and depends only on previously defined variables or $ x $.
**Objective**
For each bit position $ j \in \{1, \dots, m\} $, compute the contribution of bit $ j $ of $ x $ (denoted $ x_j \in \{0,1\} $) to the total sum of all variable values.
The total sum is linear in each bit due to the bitwise nature of operations:
$$
\text{Total Sum} = \sum_{j=1}^m 2^{m-j} \cdot f_j(x_j)
$$
where $ f_j: \{0,1\} \to \mathbb{Z} $ is the total contribution of bit $ j $ across all variables, as a function of $ x_j $.
Since each $ f_j $ is affine (linear plus constant) in $ x_j $, we can compute:
- $ c_j^0 $: total contribution of bit $ j $ when $ x_j = 0 $
- $ c_j^1 $: total contribution of bit $ j $ when $ x_j = 1 $
Then:
- To **minimize** total sum: for each $ j $, choose $ x_j = 0 $ if $ c_j^0 \le c_j^1 $, else $ x_j = 1 $.
If $ c_j^0 = c_j^1 $, choose $ x_j = 0 $ (minimum number).
- To **maximize** total sum: for each $ j $, choose $ x_j = 1 $ if $ c_j^1 \ge c_j^0 $, else $ x_j = 0 $.
If $ c_j^1 = c_j^0 $, choose $ x_j = 0 $ (minimum number).
**Output**
Two $ m $-bit binary strings:
1. The minimizing $ x $
2. The maximizing $ x $
(Each bit computed independently via static evaluation of $ f_j(0) $ and $ f_j(1) $.)