B. Побитовая формула
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вася недавно прочитал о битовых операциях, которые используются в компьютерах: AND, OR и XOR. Он неплохо изучил их свойства и придумал новую игру. Изначально Вася выбирает разрядность m для своей игры, это значит, что все числа в игре будут состоять из m битов. Потом он просит Петю выбрать некоторое одно m-битное число. После этого Вася вычисляет значения n переменных. Каждой из переменных присваивается либо константное m-битное число, либо результат выполнения битовой операции, операндами которой могут являться уже определенные переменные или выбранное Петей число. После этого сумма очков, которую получает Петя, равна сумме значений всех переменных.

Вася хочет узнать, какое число должен выбрать Петя, чтобы получить минимально возможное число очков, и какое число он должен выбрать, чтобы получить максимальное число очков. В обоих случаях, если у Пети есть несколько способов получить такую сумму, найдите минимальное число, которое он может выбрать.

Входные данные

В первой строке содержатся два целых числа n и m — количество переменных и разрядность, соответственно (1 ≤ n ≤ 5000; 1 ≤ m ≤ 1000).

В следующих n строках содержится описание переменных. В каждой строке описывается ровно одна переменная. Описание имеет следующий вид: имя новой переменной, пробел, знак «:=», снова пробел, далее два варианта:

  1. Число в битовой записи длиной ровно m битов.
  2. Первый операнд, пробел, битовая операция («AND», «OR» или «XOR»), пробел, второй операнд. Каждый операнд — это либо имя уже определенной переменной, либо символ '?', обозначающий выбранное Петей число.

Имена переменных — строки из строчных латинских букв длиной не более 10 символов. Все имена переменных различны.

Выходные данные

В первой строке выведите минимальное число, которое должен выбрать Петя, чтобы сумма значений всех переменных была минимальна, во второй строке — минимальное число, которое должен выбрать Петя, чтобы сумма значений всех переменных была максимальна. Оба числа выведите в виде двоичного m-битного числа.

Примеры
Входные данные
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
Примечание

В первом тесте если Петя выбирает число 0112, то a = 1012, b = 0112, c = 0002, сумма их значений равна 8. Если же он выберет число 1002, то a = 1012, b = 0112, c = 1112, сумма их значений равна 15.

Для второго теста минимальная и максимальная суммы переменных a, bb, cx, d и e равны 2 и не зависят от загаданного числа, поэтому минимальное число, которое может выбрать Петя — 0.