D. Өлгүүр

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

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

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

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

Нэгэн том бөгөөд олны итгэлийг хүлээсэн компани дотор хүрэм өлгөх олон тооны өлгүүрүүд бүхий нэгэн том өлгүүр байжээ. Уг том өлгүүр нь $n$ ширхэг өлгүүрээс тогтох бөгөөд эдгээр нь нэг мөрийн дагуу байрласан байх юм. Өлгүүрүүд нь зүүнээс баруун хүртэл 1-ээс $n$ хүртэлх эерэг бүхэл тоонуудаар дугаарлагдсан байна.

Компанийн ажилчид маш төвөгтэй ажлын хуваарьтай байв. Ажлын өдрийн эхэнд бүх ажилчид ажил дээрээ байхгүй байх бөгөөд том өлгүүр дээрх өлгүүрүүд нь хоосон байх юм. Хугацааны ямар нэгэн мөчид ажилчид ажил дээрээ ирэх бөгөөд мөн зарим ажилчид ажлаасаа явж байна.

Ямар нэгэн ажилчин ажил дээрээ ирэх үед тэрээр өөрийн хүрмээ аль нэгэн боломжит өлгүүр дээр өлгөнө. Бусад ажлын хамт олондоо аль болох бага хүндрэл учруулж байхаар өөрийн хүрмээ өлгөх ба ингэхдээ дараах байдлаар өлгөнө. Эхлээд тэрээр нэг мөрний дагуу байрлаж буй хүрэм өлгөж болох өлгүүрүүдийн хамгийн урт нэгэн сегментийг сонгоно. Хэрэв ийм байх хэд хэдэн сегмент байвал тэрээр баруун талтайгаа хамгийн ойр байх сегментийг сонгох юм. Үүний дараа тэрээр өөрийн хүрмээ уг сегментийн голын өлгүүр дээр өлгөх юм. Хэрэв сегмент нь тэгш тооны өлгүүр агуулж байвал тэрээр голын 2 өлгүүрийн баруун талтайгаа илүү ойрхон байрлах өлгүүр дээр хүрмээ өлгөнө.

Ажилчин явах үедээ өөрийн хүрмээ авж явна. Бүх ажилчид нэг нэгнээ гүнээсээ хүндэтгэдэг учраас хэн ч өөрийн хүний хүрмийг авч явахгүй байна.

Цаг өнгөрөх тусам уг олны итгэлийг хүлээсэн компанийн захирал уйдаж эхэлсэн бөгөөд өөрийн нарийн бичгээ $i$-р өлгүүрээс $j$-р өлгүүр хүртэл(эдгээр өлгүүрүүдийг мөн тооцно) нийтдээ хэчнээн хүрэм өлгөгдсөн байгааг олж мэдэхээр явуулжээ. Уг хүсэлтийг нарийн бичиг нь заавал биелүүлэх ёстой бөгөөд эс бөгөөс захирал уурлах ба сэтгэл санааны хямралд орох юм.

Захирлын өрөөнөөс том өлгүүр хүртэл дахин дахин явж их цаг үрэхгүйн тулд түүний нарийн бичиг танаас уг компанийн том өлгүүрийн үйл явцыг дүрслэх нэгэн программ бичиж өгөхийг хүсжээ.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$, $q$ ($1 ≤ n ≤ 10^{9}$, $1 ≤ q ≤ 10^{5}$) өгөгдөх ба эдгээр нь харгалзан том өлгүүр дээрх өлгүүрийн тоо болон хүсэлтийн тоог илэрхийлнэ. Дараа нь хүсэлтүүдийг агуулах $q$ ширхэг мөр өгөгдөх ба эдгээр нь цаг хугацааны дарааллаар өгөгдөх юм. "$0$ $i$ $j$" ($1 ≤ i ≤ j ≤ n$) гэсэн төрлийн хүсэлт нь захирлын хүсэлтийг илэрхийлнэ. Мөн оролтын өгөгдөлд дор хаяж нэг ширхэг захирлын хүсэлт өгөгдсөн байна. Бусад тохиолдолд хүсэлтүүд нь $10^{9}$-өөс хэтрэхгүй нэгэн эерэг бүхэл тоо агуулах ба энэ нь ажилчны тодорхойлолт байх юм. Сондгой ажилчны тодорхойлолт болгон нь уг ажилчин ажил дээрээ ирж байгааг илэрхийлнэ. Харин тэгш ажилчны тодорхойлолт болгон нь уг ажилчин явж байгааг илэрхийлэх юм. Бүх ажилчид нь ялгаатай тодорхойлолттой байна. Мөн ямар ч ажилчин ажил дээрээ ирэх үед дор хаяж нэг ширхэг хоосон өлгүүр байх юм.

Гаралт

Оролтод өгөгдөх захирлын хүсэлт болгоны хувьд ганц мөрөнд нэг тоог хэвлэх бөгөөд уг тоо нь $i$-р өлгүүрээс $j$-р өлгүүр хүртэл(эдгээр өлгүүрүүдийг мөн тооцно) хэчнээн хүрэм өлгөгдсөн байгааг илэрхийлэх юм.

Орчуулсан: Баатархүү

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

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