E. Бяцхан одой морь ба лорд Тайрэк

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

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

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

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

Лорд Тайрэк нь центавр бөгөөд "Миний бяцхан одой морь: Ид шидтэй нөхөрлөсөн нь" цувралын дөрөвдүгээр бүлгийн сүүлийн ангийн гол дайсны дүр юм. "Бүрэнхийн вант улс" (1-р хэсэг)-д Тайрэк Тартарусаас зугтаж одой морьдын ид шидийг шавхаж илүү хүчтэй болдог.

Тайрэкийн гол чадвар нь Мана сорох гэдэг нэртэй. Энэ нь ид шидтний бүх манаг авдаг.

Одоо бодлогоо хялбаршуулаад $n$ одой морь (1-ээс $n$ хүртэл дугаартай) байсан гэж үзье. Одой морь бүр гурван онцлог шинжтэй:

  • $s_{i}$ : хугацааны 0 агшинд тухайн одой моринд байх мана;
  • $m_{i}$ : одой моринд байж болох хамгийн их мана;
  • $r_{i}$ : нэгж хугацаанд нэмэгдэх мананы хэмжээ.

Лорд Тайрэк $m$ тушаал өгөх бөгөөд Тэдгээр нь тус бүртээ $t_{i}, l_{i}, r_{i}$ тоонуудаар илэрхийлэгднэ. Уг тушаал нь хугацааны $t_{i}$ агшинд, Тайрэк $l_{i}$-ээс $r_{i}$ (хоюулаа орно) дугаартай одой морьдод Мана сорох чадвараа хэрэглэнэ гэсэн утгатай. Эдгээр $m$ тушаалыг өгснөөр тушаал бүрийн дараа Тайрэк хэдэн мана нэмж сорохыг тооцоол.

Оролт

Эхний мөрөнд одой морьдын тоо болох $n$ ($1 ≤ n ≤ 10^{5}$) бүхэл тоо байрлана. Дараагийн $n$ мөр бүр одой морьдын онцлогийг илэрхийлэх $s_{i}, m_{i}, r_{i}$ $(0 ≤ s_{i} ≤ m_{i} ≤ 10^{5}; 0 ≤ r_{i} ≤ 10^{5})$ гурван бүхэл тоог агуулна.

Дараагийн мөрөнд тушаалын тоо болох $m$ ($1 ≤ m ≤ 10^{5}$) бүхэл тоо байрлана. Үүний дараагийн $m$ мөр бүр Лорд Тайрэкийн тушаалыг илэрхийлэх $t_{i}, l_{i}, r_{i}$ $(0 ≤ t_{i} ≤ 10^{9}; 1 ≤ l_{i} ≤ r_{i} ≤ n)$ тоонуудыг агуулна. Тушаалууд дахь $t_{i}$ (бүх $t_{i}$ тоонууд ялгаатай) тоонууд эрс өсөх байдлаар өгөгднө.

Гаралт

Тушаал бүрийн хувьд нэг мөрөнд энэ тушаалаар сорсон мананы хэмжээ болох бүхэл тоог гарга.

Орчуулсан: Sugardorj

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

Оролт
5
0 10 1
0 12 1
0 20 1
0 12 1
0 10 1
2
5 1 5
19 1 5
Гаралт
25
58

Тэмдэглэл

Одой морь бүр тэг манатай эхэлнэ. Эхний тушаалаар ганц эвэрт бүр 5 манатай болсон байх тул нийт 25 мана сорж, энэ тушаалын дараа одой морьд бүгд 0 манатай болно.

Хоёрдугаар тушаалаар, 3 дахь одой морь 14 манатай болж бусад нь бүгд тус бүртээ өөрсдийн $m_{i}$ манатай болсон байна.

Сэтгэгдлүүдийг ачааллаж байна...