B. Ангараг гаригийн уран барилга

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

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

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

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

Крис туулай эртний Ангарагчуудын соёл иргэншлийн ул мөр олжээ. Зоригтой одон орон судлаач маань нэгэн бяцхан телескоп ашиглан "Нар уруу хүрэх зам" гэх уран барилгын гайхамшигтай бүтээлийг олж харжээ. Уг барилга нь ижил хэмжээ бүхий куб хэлбэртэй чулуунууд дээр байрлаж байв. Барилгын суурь нь бүтэн "зам"-ыг нүднүүдэд хуваасан байх бөгөөд эдгээр нүднүүдэд куб хэлбэртэй чулуунууд нь яг таарч байх юм. Түүнчлэн суурин дээр байрлах нүд болгонд координат харгалзуулж болно. Овгийн ахлагч болохын тулд Ангарагын хүн нар уруу хүрэх зам барих хэрэгтэй болдог бөгөөд ингэхийн тулд өгөгдсөн суурин дээр эдгээр куб хэлбэртэй чулуунуудыг ашиглан шат үүсгэх хэрэгтэй болдог байв. Уг шат нь эхлэлийн цэг дээрх чулууны тоо ба шатны эхлэл болон төгсгөлийн координатуудаар дүрслэгдэх юм. Координатын өсөх дарааллаар байрласан шатны нүднүүдийн хувьд дараагийн нүд нь өмнө байрласан нүднээсээ 1-ээр их куб хэлбэртэй чулуу агуулах ёстой ажээ. Хэрэв ямар нэгэн нүд нь аль хэдийн хэсэг чулуунууд агуулсан байвал бид үүнийг шат үүсгэх үйл явцад тооцохгүй бөгөөд шатыг уг чулуунууд дээр үүсгэх юм. Өөрөөр хэлбэл шатны эхлэл $l$ гэсэн координаттай, төгсгөл нь $r$ гэсэн координаттай ба эхлэлийн цэг дээрх чулуу нь $x$ гэж үзье. Тэгвэл бид $l$ гэсэн нүдэн дээр $x$ ширхэг чулуу нэмж байрлуулна, $l + 1$ гэсэн нүдэн дээр $x + 1$ ширхэг чулуу нэмж байрлуулна, ..., $r$ гэсэн нүдэн дээр $x + r - l$ ширхэг чулуу байрлуулах юм.

Крис нэгэн эртний бичээс олсон бөгөөд уг бичээст бүх шатуудын тайлбарыг бичсэн байжээ. Одоо тэрээр үнэхээр "Нар уруу хүрэх зам"-ыг олсон гэдгээ мэдэхийн тулд өөрт байгаа мэдээллүүдээ харьцуулж үзэхээр болов. Ингэхийн тулд тэрээр хэсэг нүднүүдийн зам сонгох ба Ангарагын түүхийн турш уг нүднүүд дээр нэмж байрлуулсан куб хэлбэртэй чулуунуудын нийт тоог тоолох бөгөөд танийг уг олсон бичээсийг ашиглан уг нийт тоо нь онолын үүднээс ямар тоотой тэнцүү байх ёстойг олж өгөхийг хүсжээ.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан 3 бүхэл тоо $n, m, k$ ($1 ≤ n, m ≤ 10^{5}, 1 ≤ k ≤ min(n, 100)$) өгөгдөх ба эдгээр нь харгалзан нүднүүдийн тоо, "Нар уруу хүрэх зам"-уудын тоо болон асуулт дахь нүдний тоог илэрхийлнэ. Дараагийн $m$ мөрийн мөр болгонд зайгаар тусгаарлагдсан 3 бүхэл тоо $a_{i}, b_{i}, c_{i}$ ($1 ≤ a_{i} ≤ b_{i} ≤ n, 1 ≤ c_{i} ≤ 1000$) өгөгдөх ба эдгээр нь шатны тайлбар байх бөгөөд харгалзан эхлэл болон төгсгөлийн цэгүүдийн координатууд болон эхлэлийн цэг дээрх чулууны тоог илэрхийлнэ. Дараагийн мөрөнд зайгаар тусгаарлагдсан $k$ ширхэг ялгаатай бүхэл тоонууд $b_{i}$-ууд өгөгдөнө. Эдгээр тоонууд нь $1$-ээс $n$-ын хооронд байх бөгөөд Крис-ын сонирхож байгаа нүднүүдэд тавих чулуунуудын тоог илэрхийлнэ.

Гаралт

Крис-ын сонирхож буй бүх нүднүүд дээрх чулуунуудын нийлбэрийг дан мөрөнд хэвлэнэ үү.

C++ дээр 64-битийн бүхэл тоонуудыг унших болон бичихдээ %lld тодорхойлогчийг бүү хэрэглэнэ үү. Та cin эсвэл %I64d тодорхойлогчийг хэрэглэхийг илүүд үзнэ үү.

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

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

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