在过去 24 小时内,Hamed 和 Malek 全部时间都在玩“Sharti”。现在他们太累了,无法完成最后一轮。所以他们请你帮忙决定这一轮的获胜者。
“Sharti”是在 n × n 的棋盘上玩的,其中一些单元格颜色为白色,其他单元格颜色为黑色。棋盘的行从上到下使用数字 1 到 n 进行编号。此外,棋盘的列从左到右使用数字 1 到 n 进行编号。位于第 i 行和第 j 列交叉点的单元格表示为 (i, j)。
玩家轮流轮流。在每一回合中,玩家必须选择一个边长至多为 k 的正方形,并将其右下单元格涂成白色。然后该正方形中所有单元格的颜色都会反转(白色单元格变为黑色,反之亦然)。无法在轮到他执行动作的玩家就输了。
你知道哈米德和马利克非常聪明,他们会在每个回合都发挥出最好的动作。知道这一点以及哈米德先行的事实,考虑到输入中描述的初始棋盘,您必须确定其中哪一个将成为获胜者。
输入
在此问题中,初始板被指定为一组 m 个矩形。位于这些矩形中至少一个的所有单元格都涂成白色,其余单元格涂成黑色。
输入的第一行跟随三个空格分隔的整数n、m、k(1≤k≤n≤109,1≤m≤5·104),分别表示游戏过程中棋盘的大小、矩形的数量和回合方格的最大尺寸。
在接下来的 m 行的第 i 行中,给出了四个空格分隔的整数 ai, bi, ci, di (1 ≤ ai ≤ ci ≤ n, 1 ≤ bi ≤ di ≤ n),这意味着确定初始棋盘的第 i 个矩形是一个左上角单元格位于 (ai, bi) 且右下单元格位于 (ci, di) 的矩形。
输出
如果 Hamed 获胜,则打印“Hamed”,否则打印“Malek”(不带引号)。
示例
输入 #1
5 2 1 1 1 3 3 2 2 4 4
输出 #1
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
输出 #2
Hamed