D. Газрын зураг

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

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

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

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

$n×m$ тэгш өнцөгт матриц бүхий бүс нутгийн газрын зураг өгөгдөв. Матрицын нүд бүрт харгалзах хэсэг газрын дундаж өндөр агуулагдана. Петр энэхүү бүс нутагт хэд хэдэн хот барих гэж буй нэгэн компанид ажилладаг. Хот бүр нь газрын зурагт тэгш өнцөгт хэлбэртэй $a×b$ нүднүүдийг эзэмшинэ. Тодорхой нэг газарт барилгын ажлыг эхлүүлэхийн тулд Петр шинэ хот босох гэж буй барилгын талбайгаас хэт өндөр байгаа газрыг устгана. Ингэхийн тулд тэрээр талбай дахь хамгийн нам нүдийг сонгоод уг талбайд орших, үүнээс бусад нүднүүдийг энэхүү хамгийн бага түвшинд хүртэл нь намсгана. $h_{2}$-оос $h_{1}$ ($h_{1}≤h_{2}$) газрын түвшин хүртэл бууруулахын тулд тэд $h_{2}-h_{1}$ нэгж газрыг устгах хэрэгтэй болдог гэж үзье.

Хэрэв талбайгаас устгагдсан газрын хэмжээ нь бусад боломжит байршлуудтай харьцуулахад хамгийн бага бол уг талбайн байршлыг оновчтой гэж нэрлэе. Петр дараах алгоритмын дагуу хотыг барина: бүх оновчтой талбайн байршлуудаас тэр хамгийн дээр орших нэгийг сонгоно. Хэрэв байршил нь онцгой биш бол тэр хамгийн зүүн талын нэгийг сонгоно. Үүний дараагаар тэрээр уг талбайд хот барина. Петр энэ процессыг ядаж дахин нэг хот барьж болох хүртлээ давтана. Мэдээж тэр эзэнтэй нүдэнд барилгын ажил хийж чадахгүй. Та Петрт алгоритмын дагуу хотуудыг байгуулахад туслах уу?

Оролт

Эхний мөр нь хоосон зайгаар тусгаарлагдсан 4 бүхэл тоог агуулна. Үүнд: газрын зургийн хэмжээ $n$, $m$ болон хотуудын хэмжээ $a$, $b$ ($1≤a≤n≤1000$, $1≤b≤m≤1000$). Дараагийн $n$ мөрүүд тус бүр матрицын өндрийг харуулах $m$ ширхэг, сөрөг биш, хоосон зайгаар тусгаарлагдсан бүхэл тоонуудыг агуулна. Тоонууд нь $10^{9}$-аас хэтрэхгүй.

Гаралт

Эхний мөрөнд баригдсан хотуудын хэмжээг харуулах $k$ тоог хэвлээрэй. Дараагийн $k$ мөрүүдэд дараагийн барилгын талбайн зүүн-дээд булангийн мөр, баганы дугаар болон үүнээс устгах газрын хэмжээг харуулах 3 ширхэг хоосон зайгаар тусгаарлагдсан тоог хэвлээрэй. Талбайнуудыг баригдах дарааллаар нь хэвлээрэй.

Орчуулсан: Солонго

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

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