Өндөр барилгууд

Програмчлалын хамгийн мундаг аварга нь "Про Лигийн Аварга" гэдгийг мэдэх үү?

"Про Лиг" -ийн мундаг залуус их хотын өндөр барилгатай газруудаар аялах дуртай гэдгийг нь бас мэдэх үү?

Мундаг залуус энэ удаагийн зугаалгаараа хаашаа ч юм бэ нэг тийш явчихжээ. Гэхдээ тэд бидэнд өөрсдийн очсон газрынхаа зургийг явуулсан байна.

Даанч энэ зураг нь нар жаргаж байх үеийн зураг болохоор ямар газар болох нь сайн танигдахгүй байгаа. Гэхдээ уг зурган дээр бидний сонирхлыг татаж буй нэг зүйл бий. Бид зургийг $N$ тэнцүү хэсэгт хуваагаад $1$-ээс $N$ хүртэл дугаарлая. Тэгвэл хэсэг бүрийн хамгийн өндөр барилгын өндрийг нь олоорой.

Оролт

Эхний мөрөнд зургийг хэдэн хэсэгт хуваасныг илэрхийлэх $N$ болон зурган дээр байгаа барилгын тоо $M$ өгөгдөнө.
Дараагийн $M$ мөрөнд барилга тус бүрийг илэрхийлэх $l_i, r_i, h_i$ тоонууд өгөгдөнө. Барилга тус бүр тэгш өнцөгт хэлбэртэй ба дээрх тоонууд нь $i$-р барилга зургийн $l_i$-р хэсгээс эхэлж $r_i$-р хэсэг хүртэл $h_i$ өндөртэйгээр үргэлжилнэ гэдгийг илэрхийлнэ.

Гаралт

$N$ мөрөнд хэсэг бүрийн хамгийн өндөр барилгын өндрийг хэвлэнэ.

Жишээ тэст 1
Оролт
$10\ 5\\ 1\ 5\ 3\\ 3\ 7\ 4\\ 5\ 6\ 8\\ 1 \ 9\ 1\\ 1\ 1\ 10$
Гаралт
$10\\ 3\\ 4\\ 4\\ 8\\ 8\\ 4\\ 1\\ 1\\ 0$
Тайлбар
Дээрх жишээний хувьд зураг дээрх эхний барилга $1$-р хэсгээс $5$-р хэсэг хүртэл $3$ өндөртэй, $2$-дахь барилга $3$-р хэсгээс $7$-р хэсэг хүртэл $4$ өндөртэй, $3$-дахь барилга $5$-р хэсгээс $6$-р хэсэгт $8$ өндөртэй, $4$-дахь барилга $1$-р хэсгээс $9$-р хэсэг хүртэл $1$ өндөртэй, сүүлийн барилга $1$-р хэсгээс $1$-р хэсэг хүртэл $10$ өндөртэй байна. Эдгээр барилгууд доорх зураг шиг харагдана.