Вася недавно прочитал о битовых операциях, которые используются в компьютерах: AND, OR и XOR. Он неплохо изучил их свойства и придумал новую игру. Изначально Вася выбирает разрядность m для своей игры, это значит, что все числа в игре будут состоять из m битов. Потом он просит Петю выбрать некоторое одно m-битное число. После этого Вася вычисляет значения n переменных. Каждой из переменных присваивается либо константное m-битное число, либо результат выполнения битовой операции, операндами которой могут являться уже определенные переменные или выбранное Петей число. После этого сумма очков, которую получает Петя, равна сумме значений всех переменных.
Вася хочет узнать, какое число должен выбрать Петя, чтобы получить минимально возможное число очков, и какое число он должен выбрать, чтобы получить максимальное число очков. В обоих случаях, если у Пети есть несколько способов получить такую сумму, найдите минимальное число, которое он может выбрать.
Выходные данные
В первой строке выведите минимальное число, которое должен выбрать Петя, чтобы сумма значений всех переменных была минимальна, во второй строке — минимальное число, которое должен выбрать Петя, чтобы сумма значений всех переменных была максимальна. Оба числа выведите в виде двоичного m-битного числа.
Примечание
В первом тесте если Петя выбирает число 0112, то a = 1012, b = 0112, c = 0002, сумма их значений равна 8. Если же он выберет число 1002, то a = 1012, b = 0112, c = 1112, сумма их значений равна 15.
Для второго теста минимальная и максимальная суммы переменных a, bb, cx, d и e равны 2 и не зависят от загаданного числа, поэтому минимальное число, которое может выбрать Петя — 0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
a := 101
b := 011
c := ? XOR b
|
011
100
|
|
2
|
5 1
a := 1
bb := 0
cx := ? OR a
d := ? XOR ?
e := d AND bb
|
0
0
|