发现本题为公平组合游戏，考虑用 \(\text{SG}\) 函数来解决。

对于翻硬币游戏，一个状态的 \(\text{SG}\) 值为当前状态的每个正面朝上的硬币单一存在时的 \(\text{SG}\) 值的异或和。

可以用归纳法得到位置 \((x,y)\) 的 \(\text{SG}\) 值：

\[\large\text{SG}(x,y)=\min\{\text{lowbit}(x),\text{lowbit}(y) ,\text{greatbit}(k)\} \]

那么每个位置的 \(\text{SG}\) 值都是 \(2^t\) 的形式。

考虑如何计算区间 \([l,r]\) 的 \(\text{lowbit}\) 的异或和，得 \(i\) 作为 \(\text{lowbit}\) 的贡献次数为：

\[\large\frac{r}{i}-\frac{l-1}{i}-\left(\frac{r}{2i}-\frac{l-1}{2i}\right) \]

前一项为所有情况，后一项为 \(i\) 不为 \(\text{lowbit}\) 的情况。

可以用扫描线来分别统计行和列的答案，然后再合并。直接算 \(\text{SG}\) 值等于 \(2^t\) 的个数不好算，可以算出 \(\geqslant2^t\) 的个数，等于 \(2^t\) 的个数作差即可求得。

#include<bits/stdc++.h>
#define maxn 100010
#define maxm 3000010
#define mid ((l+r)>>1)
using namespace std;
template<typename T> inline void read(T &x)
{
    x=0;char c=getchar();bool flag=false;
    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    if(flag)x=-x;
}
int n,m,k,lim=1,t,ans,root,tot,cnt;
int num[maxn],ls[maxm],rs[maxm],tag[maxm],sum[maxm],val[maxm];
struct node
{
    int x,l,r,v;
}p[maxn];
bool cmp(const node &a,const node &b)
{
    return a.x<b.x;
}
int get(int l,int r)
{
    int v=0;
    for(int i=1;i<=k;i<<=1)
        v|=(((r/i-(l-1)/i)-(i*2<=k?r/i/2-(l-1)/i/2:0))&1)*i;
    return v;
}
void pushup(int cur,int l,int r)
{
    if(tag[cur]) sum[cur]=val[cur];
    else sum[cur]=sum[ls[cur]]^sum[rs[cur]];
}
void modify(int L,int R,int l,int r,int v,int &cur)
{
    if(!cur) cur=++tot;
    val[cur]=get(l,r);
    if(L<=l&&R>=r)
    {
        tag[cur]+=v,pushup(cur,l,r);
        return;
    }
    if(L<=mid) modify(L,R,l,mid,v,ls[cur]);
    if(R>mid) modify(L,R,mid+1,r,v,rs[cur]);
    pushup(cur,l,r);
}
int main()
{
    read(n),read(m),read(k);
    while(lim<=k) lim<<=1,t++;
    for(int i=1;i<=m;++i)
    {
        int u,d,l,r;
        read(l),read(u),read(r),read(d);
        p[++cnt]={l,u,d,1},p[++cnt]={r+1,u,d,-1};
    }
    sort(p+1,p+cnt+1,cmp);
    for(int i=1;i<=cnt;++i)
    {
        if(p[i-1].x!=p[i].x)
        {
            int v1=sum[root],v2=get(p[i-1].x,p[i].x-1),s1=0,s2=0;
            for(int j=lim,l=t;j;j>>=1,l--)
                s1+=((v1&j)!=0),s2+=((v2&j)!=0),num[l]+=s1*s2;
        }
        modify(p[i].l,p[i].r,1,n,p[i].v,root);
    }
    for(int i=0,j=1;i<t;++i,j<<=1)
        if((num[i]-num[i+1])&1)
            ans^=j;
    if(ans) puts("Hamed");
    else puts("Malek");
    return 0;
}