91E орчуулах · Codeforces.mn

# Тэнгэр баганадсан барилга
Өнөөдөр Хойд туйл “Тэнгэр баганадсан барилга” хэмээх тоглоомын төрлөөр олимпийн наадмыг зохион байгуулж байна. $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$ тооны далайн морины тоог хэвлэ. Мөр тус бүрт нэгийг хэвлэ.

-- Энхгэрэл

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

Оролт

Гаралт

Оролт

Гаралт