E. Тэнгэр баганадсан барилга

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

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

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

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

Өнөөдөр Хойд туйл “Тэнгэр баганадсан барилга” хэмээх тоглоомын төрлөөр олимпийн наадмыг зохион байгуулж байна. $n$ тооны далайн моринууд наадамд өрсөлдөж байна. Далайн моринуудад $1$-ээс $n$ хүртэл ер бусын тоо өгөв. Эхлэх дохио өгөхөд далайн моринууд өөрийн тэнгэр баганадсан барилгаа барьж эхэлнэ. Цаг $0$ болох мөчид $i$ дахь далайн морины тэнгэр баганадсан барилга $a_{i}$-тэй тэнцүү өндөртэй байлаа. Минут тутамд $i$ дахь далайн морь $b_{i}$ давхруудыг хийж дуусгаж байв.

Олимп болж буй газраас шууд сурвалжилж байсан сурвалжлагчид зохион байгуулагчдад $q$ тооны асуулга тавьжээ. Асуулга бүр нь $l_{i}$, $r_{i}$, $t_{i}$ гэсэн гурван тооны багцаар илэрхийлэгдсэн байв.

Асуулга бүрт зохион байгуулагчид $x$ гэсэн тоогоор хариулт өгөв. Үүнд:

1. $x$ тоо нь $l_{i}$ to $r_{i}$-ээс ($l_{i} ≤ x ≤ r_{i}$)-ийг хүртэл интерваль дээр байрлана.

2. $x$ дугаартай далайн морины барилга бусад далайн моринуудын барилгаас хамгийн өндөр нь $t_{i}$ хугацааны агшинд $[l_{i}, r_{i}]$ интервалд байна.

Сурвалжлагч тус бүрийн асуулгад дээрх шалгуурыг хангасан $x$ тооны далайн морины тоог хэвлэ. Хэрэв хэд хэдэн боломжит хариу гарвал нэг хариуг хэвлэнэ үү.

Оролт

Эхний мөр нь $n$ болон $q$ ($1 ≤ n, q ≤ 10^{5}$) гэсэн хоёр бүхэл тоо агуулна. Дараагийн мөр нь $a_{i}$, $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ 10^{9}$) гэсэн хос тоо агуулна. Үүний дараа $q$ асуулга $l_{i}$, $r_{i}$, $t_{i}$ хэлбэртэй орох ба мөр тус бүрт ($1 ≤ l_{i} ≤ r_{i} ≤ n$, $0 ≤ t_{i} ≤ 10^{6}$) байна. Оролтын бүх тоо нь бүхэл тоо байна.

Гарал

Сурвалжлагч тус бүрийн асуулгад дээрх шалгуурыг хангасан $x$ тооны далайн морины тоог хэвлэ. Мөр тус бүрт нэгийг хэвлэ.

Орчуулсан: Энхгэрэл

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

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