E. Шарти
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Хамед и Малек провел последние 24 часа за игрой в «Шарти». Они очень устали и не могут завершить последний раунд. Поэтому они попросили Вас помочь им определить победителя этого раунда.

«Шарти» играется на доске размера n × n, клетки которой покрашены в белый и чёрный цвета. Строки доски пронумерованы сверху вниз номерами от 1 до n. Столбцы доски пронумерованы слева направо номерами от 1 до n. Клетка, расположенная на пересечении i-го ряда и j-го столбца обозначается как (i, j).

Игроки ходят по очереди. За свой ход игрок должен выбрать квадрат с длиной стороны не больше k, правая нижняя клетка которого покрашена в белый цвет. Затем цвета всех клеток в этом квадрате инвертируются (белые клетки становятся черными и наоборот). Игрок, который не может сделать ход, когда подходит его очередь, проигрывает.

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

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

В этой задаче исходная доска задаётся множеством из m прямоугольников. Все клеточки, находящиеся хотя бы в одном из этих прямоугольников, окрашены в белый цвет, а остальные окрашены черным.

В первой строке ввода следуют три целых числа через пробел n, m, k (1 ≤ k ≤ n ≤ 109, 1 ≤ m ≤ 5·104) — размер доски, количество прямоугольников и максимальный размер квадрата, доступного игроку во время его хода, соответственно.

В i-й из следующих m строк записано четыре целых числа через пробел ai, bi, ci, di (1 ≤ ai ≤ ci ≤ n, 1 ≤ bi ≤ di ≤ n), обозначающих, что i-й прямоугольник, описывающий исходную доску, это прямоугольник с левой верхней клеточкой в (ai, bi) и правой нижней клеточкой в (ci, di).

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

Если выигрывает Хамед, выведите «Hamed», в противном случае выведите «Malek» (без кавычек).

Примеры
Входные данные
5 2 1
1 1 3 3
2 2 4 4
Выходные данные
Malek
Входные данные
12 5 7
3 4 5 6
1 2 1 2
4 5 9 9
8 6 12 10
12 4 12 4
Выходные данные
Hamed