Хамед и Малек провел последние 24 часа за игрой в «Шарти». Они очень устали и не могут завершить последний раунд. Поэтому они попросили Вас помочь им определить победителя этого раунда.
«Шарти» играется на доске размера n × n, клетки которой покрашены в белый и чёрный цвета. Строки доски пронумерованы сверху вниз номерами от 1 до n. Столбцы доски пронумерованы слева направо номерами от 1 до n. Клетка, расположенная на пересечении i-го ряда и j-го столбца обозначается как (i, j).
Игроки ходят по очереди. За свой ход игрок должен выбрать квадрат с длиной стороны не больше k, правая нижняя клетка которого покрашена в белый цвет. Затем цвета всех клеток в этом квадрате инвертируются (белые клетки становятся черными и наоборот). Игрок, который не может сделать ход, когда подходит его очередь, проигрывает.
Вы знаете, что Хамед и Малек очень умные и они действуют оптимальным образом. Зная это и то, что Хамед ходит первым, а также имея описание исходной доски во входных данных, определите, кто из них победит.
Выходные данные
Если выигрывает Хамед, выведите «Hamed», в противном случае выведите «Malek» (без кавычек).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2 1
1 1 3 3
2 2 4 4
|
Malek
|
|
2
|
12 5 7
3 4 5 6
1 2 1 2
4 5 9 9
8 6 12 10
12 4 12 4
|
Hamed
|