套路题，棋盘博弈套矩形并。

棋盘博弈有个结论，每个可以翻的棋子可以认为是单独一个互不影响的子游戏。

换言之，对于每个染了色的棋子，只要考虑一个仅包含该棋子的游戏局面，求出该局面的 SG 值，然后将所有这样的 SG 值异或起来就是整个游戏的 SG 值。

考虑求出仅含一个染色棋子 $(x, y)$ 的 SG 值（以下部分没有证明）。

先忽略 $k$ 的限制。

有个被出烂的博弈结论：

• 假设棋盘是一个长条，那么在第 $x$ 个点的棋子其 SG 值为 $lowbit(x)$ 。

将这个结论推广到二维，加以归纳，可以发现忽略 $K$ 的前提下，棋子 $(x, y)$ 的 SG 值就是 $min(lowbit(x), lowbit(y))$ 。

而加上 $K$ 的限制后，第 $x$ 个点的棋子 SG 值为 $min(lowbit(x), lowbit(y), greatbit(k))$ 。

ps: 这里两个维度不是独立的，不能用 Nim 积（我第一眼把这题看成了 Boring Game 的翻版）

现在的问题是对于一个矩形并求出其 SG 值的异或和。

类似于矩形面积并，用扫描线 + 线段树进行维护。

注意到 $lowbit$ 都是 2 的整次幂，种类数是 $O(logN)$ 的，因此可以考虑在线段树中维护每个 $lowbit$ 的数量。

然后扫描线扫过一段时，同样求出这段区间每个 $lowbit$ 的数量，统计答案时只需要在两个维度 $O(log^2N)$ 分别枚举 $lowbit$ ，与 $greatbit(k)$ 一起取 min 即可算进答案。

至于求一段区间的 $lowbit$ 分布，首先转换为求一段前缀 $[0, n]$ 的 $lowbit$ 分布，数位 DP 一下或者通过逼近每个二进制位的方法可以 $O(logN)$ 实现，不在讨论重点。

时间复杂度 $O(mlog^2N)$ 。

空间复杂度 $O(mlogN)$ 。

参考实现：

#include <cstdio>
#include <algorithm>
#include <cassert>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;
struct {
    inline operator int () { int x; return scanf("%d", &x), x; }
    inline operator ll () { ll x; return scanf("%lld", &x), x; }
} read;

const int maxn = 100005, maxk = 30;
struct  Tree {
    int cover, low[maxk];
} pool[maxn << 2];
#define self pool[now]
#define lt (now << 1)
#define rt (now << 1 | 1)
int pre[maxn][maxk];

void update(int now, int L, int R) {
    if(self.cover)
        for(int k = 0; k < maxk; k ++)
            self.low[k] = pre[R][k] - pre[L - 1][k];
    else if(L == R)
        for(int k = 0; k < maxk; k ++)
            self.low[k] = 0;
    else
        for(int k = 0; k < maxk; k ++)
            self.low[k] = pool[lt].low[k] + pool[rt].low[k];
}

void modify(int now, int L, int R, int l, int r, int x) {
    if(r < L or l > R) return;
    if(l <= L and R <= r) return self.cover += x, update(now, L, R);
    int M = (L + R) >> 1;
    modify(lt, L, M, l, r, x);
    modify(rt, M + 1, R, l, r, x);
    update(now, L, R);
}

int get[maxk];
void getlow(int n) {
    std::fill(get, get + maxk, 0);
    for(int k = maxk - 1; k; k --) {
        get[k - 1] += get[k] << 1;
        if(n >> k & 1)
            ++ get[k - 1];
    }
    for(int k = 0; k < maxk; k ++)
        if(n >> k & 1)
            ++ get[k];
}

struct Operation {
    int l, r, t, o;
} op[maxn];
int tmp[maxn], tp;

int main() {
    read.operator int();
    int n = 0, m = read, K = read;
    for(int k = 0; k < maxk + 1; k ++)
        if((1 << k) > K) {
            K = 1 << k >> 1;
            break;
        }

    for(int i = 1; i <= m; i ++) {
        int lx = read, ly = read;
        int rx = read, ry = read;
        op[i * 2 - 1] = {ly, ry, lx, 1};
        op[i * 2] = {ly, ry, rx + 1, -1};
        tmp[++ n] = ly - 1;
        tmp[++ n] = ry;
    }

    std::sort(tmp + 1, tmp + n + 1);
    n = int(std::unique(tmp + 1, tmp + n + 1) - tmp - 1);
    for(int i = 1; i <= n; i ++) {
        getlow(tmp[i]);
        std::copy(get, get + maxk, pre[i]);
    }

    std::sort(op + 1, op + m * 2 + 1, [](Operation a, Operation b) {
                return a.t < b.t;
            });

    int sg = 0;
    for(int i = 1; i <= m * 2; i ++) {
        int shit[maxk];
        getlow(op[i].t - 1);
        std::copy(get, get + maxk, shit);
        getlow(op[i - 1].t - 1);
        for(int k = 0; k < maxk; k ++)
            shit[k] -= get[k];
        for(int k1 = 0; k1 < maxk; k1 ++)
            if(shit[k1] & 1)
                for(int k2 = 0; k2 < maxk; k2 ++)
                    if(pool[1].low[k2] & 1)
                        sg ^= std::min({1 << k1, 1 << k2, K});
        int l = int(std::lower_bound(tmp + 1, tmp + n + 1, op[i].l - 1) - tmp) + 1;
        int r = int(std::lower_bound(tmp + 1, tmp + n + 1, op[i].r) - tmp);
        modify(1, 1, n, l, r, op[i].o);
    }

    if(sg) puts("Hamed");
    else puts("Malek");
}