CF494E Sharti

过去的 24 小时里，Hamed 和 Malek 一直在玩 “Sharti”。现在他们已经筋疲力尽，无法完成最后一局，所以他们请你帮忙判断本局的胜者。 “Sharti” 是在一个 $n \times n$ 的棋盘上进行的，其中一些格子是白色的，其他是黑色的。棋盘的行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $n$。位于第 $i$ 行第 $j$ 列的格子记作 $(i,j)$。 两位玩家轮流行动。每回合，玩家必须选择一个边长不超过 $k$ 的正方形，其右下角格子为白色。然后，将该正方形内所有格子的颜色反转（白变黑，黑变白）。无法行动的玩家判负。 你知道 Hamed 和 Malek 都非常聪明，每一步都会采取最优策略。已知 Hamed 先手，以及棋盘的初始状态如下面的输入描述。请你判断最终获胜的是谁。

本题中，初始棋盘由 $m$ 个矩形描述。所有位于至少一个这些矩形内部的格子都是白色，其余为黑色。 输入第一行包含三个用空格分隔的整数 $n, m, k$（$1 \le k \le n \le 10^9, 1 \le m \le 5 \times 10^4$），分别表示棋盘的大小、矩形的数量及每轮允许操作的正方形最大边长。 接下来 $m$ 行，每行四个用空格分隔的整数 $a_i, b_i, c_i, d_i$（$1\le a_i \le c_i \le n, 1\le b_i \le d_i \le n$），表示第 $i$ 个矩形的左上角坐标 $(a_i, b_i)$ 和右下角坐标 $(c_i, d_i)$，这些矩形共同决定初始棋盘。

如果 Hamed 获胜，输出 "Hamed"；否则输出 "Malek"（不包括引号）。

由 ChatGPT 5 翻译