E. Шарти

хугацааны хязгаарлалт 5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Хамед, Малек хоёр сүүлийн 24 цагийг "Шарти" гэх тоглоомоор тоглон өнгөрүүлжээ. Тэд хэтэрхий ядарсан тул сүүлийн тоглоомоо дуусгаж чадсангүй. Тиймээс тэд энэ өрөг дээр хэн ялсаныг шийдэхэд туслаач гэж таниас асуужээ.

"Шарти" $n × n$ хэмжээтэй зарим нүд нь цагаанаар үлдсэн нь хараар будагдсан хөлөг дээр тоглодог тоглоом юм. Хөлгийн мөрүүд нь дээрээс доошоо $1$-ээс $n$ хүртэл тоогоор тэмдэглэгдсэн. Бас багана нь $1$-ээс $n$ хүртэл тоогоор зүүнээс баруун уруу тэмдэглэгдсэн байдаг. Нүд нь $i$-р мөр болон $j$-р баганы огтлолцол дээр байрлаж $(i, j)$ тэмдэглэгддэг.

Тоглогчид ээлжээр нүүнэ. Тоглогч нүүдэл бүрд хамгийн ихдээ $k$ урттай тал бүхий квадратыг хамрах нүднүүдийг сонгоно (гэхдээ баруун доод булангийн нүд заавал цагаан байх ёстой). Үүний дараа энэ квадрат доторх нүднүүдийн өнгө эсрэгээрээ солигдоно. Нүүдэл хийх боломжгүй болсон тоглогч нь ялагдана.

Хамед, Малек хоёр маш ухаалаг бөгөөд тэд нүүдэл бүр дээр боломжит хамгийн зөв нүүдлийг хийнэ. Хамед одоо нүүх ёстой бөгөөд хөлгийн одоогийн байдал өгөгдөнө. Тийм бол хэн нь ялагч болохыг тодорхойлно уу.

Оролт

Хөлгийг дүрслэхэд $m$ ширхэг тэгш өнцөгт хэрэглэгдэнэ. Энэ тэгш өнцөгтийн бүх нүднүүд цагаан байх бөгөөд бусад нүднүүд нь хар байх юм.

Эхний мөрөнд зайгаар тусгаарлагдсан бүхэл тоо $n, m, k$ буюу талбайн хэмжээ, тэгш өнцөгтүүдийн тоо, бас квадратын хамгийн урт хэмжээ харгалзан өгөгдөнө. ($1 ≤ k ≤ n ≤ 10^{9}$, $1 ≤ m ≤ 5 \cdot 10^{4}$)

Дараагийн $m$ мөрөнд мөр бүрд $4$ тоо өгөгдөнө. $i$ дэхь мөрөнд 4-н ширхэг зайгаар тусгаарлагдсан бүхэл тоо $a_{i}, b_{i}, c_{i}, d_{i}$ ($1 ≤ a_{i} ≤ c_{i} ≤ n$, $1 ≤ b_{i} ≤ d_{i} ≤ n$) өгөгдөнө. Үүнд $i$ дэхь тэгш өнцөгтийн байрлал нь зүүн дээд булангийн нүд нь $(a_{i}, b_{i})$, харин баруун доод булангийн нүд нь $(c_{i}, d_{i})$ дээр байрлалтай байхаар өгөгдөнө.

Гаралт

Хамед ялахаар бол "Hamed" Малек ялахаар бол "Malek" гэж хэвлэнэ үү.

Орчуулсан: Энхлут

Жишээ тэстүүд

Оролт
5 2 1
1 1 3 3
2 2 4 4
Гаралт
Malek
Оролт
12 5 7
3 4 5 6
1 2 1 2
4 5 9 9
8 6 12 10
12 4 12 4
Гаралт
Hamed
Сэтгэгдлүүдийг ачааллаж байна...