CF494E.Sharti

During the last 24 hours Hamed and Malek spent all their time playing "Sharti". Now they are too exhausted to finish the last round. So they asked you for help to determine the winner of this round.

"Sharti" is played on a n × n board with some of cells colored white and others colored black. The rows of the board are numbered from top to bottom using number 1 to n. Also the columns of the board are numbered from left to right using numbers 1 to n. The cell located at the intersection of i-th row and j-th column is denoted by (i, j).

The players alternatively take turns. In each turn the player must choose a square with side-length at most k with its lower-right cell painted white. Then the colors of all the cells in this square are inversed (white cells become black and vice-versa). The player who cannot perform a move in his turn loses.

You know Hamed and Malek are very clever and they would have played their best moves at each turn. Knowing this and the fact that Hamed takes the first turn, given the initial board as described in the input, you must determine which one of them will be the winner.

在过去的 24 小时里，Hamed 和 Malek 一直都在玩“Sharti”游戏。现在他们已精疲力竭，无法完成最后一轮。因此，他们请你帮忙判断本轮的获胜者。

“Sharti”游戏在一个 $n \times n$ 的棋盘上进行，棋盘上部分格子为白色，其余为黑色。棋盘的行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $n$。位于第 $i$ 行与第 $j$ 列交叉处的格子记作 $(i,\,j)$。

两名玩家轮流行动。在每一轮中，当前玩家必须选择一个边长至多为 $k$ 的正方形区域，且该正方形的右下角格子必须为白色；然后将该正方形内所有格子的颜色翻转（即白色变为黑色，黑色变为白色）。无法进行合法操作的玩家判负。

已知 Hamed 和 Malek 都非常聪明，且在每一步均采取最优策略。已知 Hamed 先手，且给定初始棋盘状态（如输入所述），请判断两人中谁将获胜。

In this problem the initial board is specified as a set of m rectangles. All cells that lie inside at least one of these rectangles are colored white and the rest are colored black.

In the first line of input three space-spereated integers n, m, k (1 ≤ k ≤ n ≤ 109, 1 ≤ m ≤ 5·104) follow, denoting size of the board, number of rectangles and maximum size of the turn square during the game, respectively.

In i-th line of the next m lines four space-seperated integers a__i, b__i, c__i, d__i (1 ≤ a__i ≤ c__i ≤ n, 1 ≤ b__i ≤ d__i ≤ n) are given meaning that i-th rectangle determining the initial board is a rectangle with upper-left cell at (a__i, b__i) and lower-right cell at (c__i, d__i).

本题中，初始棋盘由 $m$ 个矩形指定：所有位于至少一个矩形内部的格子被染成白色，其余格子被染成黑色。

输入第一行包含三个以空格分隔的整数 $n$、$m$、$k$（$1 \leq k \leq n \leq 10^9$，$1 \leq m \leq 5 \cdot 10^4$），分别表示棋盘大小、矩形个数以及游戏中每次操作所用正方形的最大边长。

接下来 $m$ 行中，第 $i$ 行包含四个以空格分隔的整数 $a_i$、$b_i$、$c_i$、$d_i$（$1 \leq a_i \leq c_i \leq n$，$1 \leq b_i \leq d_i \leq n$），表示定义初始棋盘的第 $i$ 个矩形：其左上角格子坐标为 $(a_i, b_i)$，右下角格子坐标为 $(c_i, d_i)$。

If Hamed wins, print "Hamed", otherwise print "Malek" (without the quotes).

如果哈梅德获胜，输出 “Hamed”，否则输出 “Malek”（不带引号）。