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.
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. 1.  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.
In the first sample if Peter chooses a number 011<sub class="lower-index">2</sub>, then *a* = 101<sub class="lower-index">2</sub>, *b* = 011<sub class="lower-index">2</sub>, *c* = 000<sub class="lower-index">2</sub>, the sum of their values is 8. If he chooses the number 100<sub class="lower-index">2</sub>, then *a* = 101<sub class="lower-index">2</sub>, *b* = 011<sub class="lower-index">2</sub>, *c* = 111<sub class="lower-index">2</sub>, 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.
3 3
a := 101
b := 011
c := ? XOR b
011
100
5 1
a := 1
bb := 0
cx := ? OR a
d := ? XOR ?
e := d AND bb
0
0
2 10
b := 0100101101
a := ? XOR b
0100101101
1011010010
1 10
a := 0110110011
0000000000
0000000000
1 6
a := ? OR ?
000000
111111
13 6
a := 111010
b := 100100
c := 001110
d := b AND b
e := c AND ?
f := e OR c
g := 011110
h := d XOR ?
i := 010111
j := 000011
k := d OR ?
l := 011101
m := b OR j
100000
011011
16 3
a := 011
b := 110
c := a XOR b
d := 110
e := a XOR b
f := b XOR a
g := b XOR e
h := 111
i := a XOR h
j := f XOR ?
k := 100
l := 000
m := 100
n := 110
o := 110
p := 110
101
010
29 2
aa := 10
ba := 11
ca := 01
da := aa AND ?
ea := ba OR ?
fa := da XOR ?
ga := 11
ha := fa XOR ea
ia := 01
ja := ca OR ha
ka := ha XOR ia
la := ha OR ?
ma := ba AND ba
na := ma OR ?
oa := 11
pa := oa OR ba
qa := 00
ra := qa AND ia
sa := fa OR ?
ta := ha OR ga
ua := 00
va := 00
wa := 11
xa := 10
ya := ja XOR ?
za := 00
ab := 00
bb := pa OR qa
cb := bb AND ?
00
11
10 3
a := 011
b := ? OR a
c := 000
d := ? AND c
e := 101
f := ? AND e
g := 001
h := ? XOR g
i := 001
j := ? XOR i
001
110
12 3
a := 101
b := a XOR ?
c := b XOR b
d := b XOR a
e := c XOR ?
f := e XOR ?
g := c XOR f
h := 100
i := c XOR h
j := c XOR i
k := b XOR ?
l := 111
000
111
12 14
a := 01100010000111
b := ? XOR a
c := 01101111001010
d := ? XOR c
e := 10000011101111
f := ? XOR e
g := 10100011001010
h := ? XOR g
i := 10010110111111
j := ? XOR i
k := 10000111110001
l := ? XOR k
10000011001011
01011000010000
14 8
a := 01010000
b := 10101111
c := 01100100
d := 10011011
e := 01001100
f := 10110011
g := ? XOR a
h := b XOR ?
i := ? XOR c
j := d XOR ?
k := ? XOR e
l := f XOR ?
m := 00101111
n := ? XOR m
00101111
11010000
14 14
a := 10000100110000
b := 01111011001111
c := 11110001111101
d := 00001110000010
e := 00111100000010
f := 11000011111101
g := ? XOR a
h := b XOR ?
i := ? XOR c
j := d XOR ?
k := ? XOR e
l := f XOR ?
m := 11110011011001
n := ? XOR m
11110011011001
00001100100110
17 15
a := 010000111111110
b := 101100110000100
c := 100101100100111
d := 010110101110110
e := 111111000010110
f := 011001110111110
g := 110011010100101
h := 000001010010001
i := 110000111001011
j := 000010000010111
k := 110110111110110
l := 010000110000100
m := 000111101101000
n := 011111011000111
o := 010110110010100
p := 111001110011001
q := 000100110001000
000000000000000
000000000000000
22 9
a := 100101111
b := 010001100
c := b AND b
d := 111000010
e := c AND a
f := a OR e
g := e AND ?
h := 000010001
i := b OR ?
j := d AND ?
k := g AND h
l := 010100000
m := a AND a
n := j AND ?
o := m OR n
p := o AND ?
q := f OR ?
r := 000011011
s := 001110011
t := 100111100
u := l AND p
v := g OR h
000000000
111111111
2 109
a := 1010101010100000000000011111111111111111111111111111111111111111111000000000000000000000000000111111111111111
b := ? XOR a
1010101010100000000000011111111111111111111111111111111111111111111000000000000000000000000000111111111111111
0101010101011111111111100000000000000000000000000000000000000000000111111111111111111111111111000000000000000
f = {'OR': lambda x, y: x | y, 'AND': lambda x, y: x & y, 'XOR': lambda x, y: x ^ y}
n, m = map(int, input().split())
u, v = [], []
d = {'?': n}
for i in range(n):
    q, s = input().split(' := ')
    if ' ' in s:
        x, t, y = s.split()
        u += [(i, d[x], f[t], d[y])]
    else: v += [(i, s)]
    d[q] = i
s = [0] * (n + 1)
def g(k, j):
    s[n] = k
    for i, q in v: s[i] = q[j] == '1'
    for i, x, f, y in u: s[i] = f(s[x], s[y])
    return sum(s) - k
a = b = ''
for j in range(m):
    d = g(1, j) - g(0, j)
    a += '01'[d < 0]
    b += '01'[d > 0]
print(a, b)