C. Боловсролын тогтолцооны шинэчлэл

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

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

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

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

Саяхан Берландад боловсролын тогтолцооны шинэчлэл хийгджээ. Уг шинэчлэл нь дараах байдлаар хийгдэв:

Хичээлийн жил $n$ өдрөөс бүрдэнэ. Өдөр бүр сурагчид $m$ хичээлүүдээс яг нэгийг судалдаг ба хичээл бүрийг нэгээс илүү өдөр ордоггүй. $i$-р хичээлийн дараа сурагчид $a_{i}$-ээс их, $b_{i}$-ээс бага дасгал агуулсан гэрийн даалгавар авна. Үүнээс гадна хичээлүүд хүнд хөнгөнөөрөө адилгүй тул тухайн хичээлийн төвөгтэй байдлыг $c_{i}$-аар илэрхийлнэ. Сургуулиас дараах нөхлийг хангасан хичээлийн хуваарь зохиох боломжтой:

  • Хугацааны хувьд хичээлүүд хүндрэх дарааллаараа байрлах ёстой.

  • Эхний өдрийг эс тооцвол өдөрт өгөгдөх даалгавар нь өмнөх өдрийнхөөс $k$ дахин их юм уу, $k$-аар их дасгал агуулсан байх ёстой. Өөрөөр хэлбэл, $i$ дахь өдрийн гэрийн даалгаврын дасгалын тоог $x_{i}$ байна гэж үзвэл $i$ ($1 < i ≤ n$) бүрийн хувьд $x_{i} = k + x_{i - 1}$ эсвэл $x_{i} = k \cdot x_{i - 1}$ нөхцөл биелнэ.

  • Бүх өдрүүдэд өгөгдсөн гэрийн даалгаврын дасгалын тоонуудын нийлбэр боломжит хамгийн их тоо байх ёстой.

Сургууль тус бүр бүх хязгаарыг өөр өөрөөр тогтоосон байна. Ихэнх сургуульд $a_{i}$ болон $b_{i}$ нь $10^{16}$-д хүрсэн байна. Хэдий тийм ч Берландын Боловсролын сайд дунджийг баримтлах дуртай тул $(b_{i} - a_{i})$-ын утга нь $100$-аас хэтрэхгүй. Үүнийг Берландын 256-р сургууль дээр ч хэрэгжүүлсэн болно. Та сургуулийн захирал тул ирэх хичээлийн жилийнхээ хуваарийг зохиох ёстой болсон байна.

Оролт

Эхний мөр нь $n$, $m$, $k$ ($1 ≤ n ≤ m ≤ 50$, $1 ≤ k ≤ 100$) гэсэн гурван бүхэл тоо агуулах ба эдгээр нь хичээлийн жилийн өдрийн тоо, хичээлийн тоо болон $k$ гэсэн параметрыг тус тус агуулна. Дараагийн $m$ мөрүүд тус бүр нь $a_{i}$, $b_{i}$, $c_{i}$ ($1 ≤ a_{i} ≤ b_{i} ≤ 10^{16}$, $b_{i} - a_{i} ≤ 100$, $1 ≤ c_{i} ≤ 100$) гэсэн гурван бүхэл тоогоор илэрхийлэгдсэн хичээлийн тодорхойлолтыг агуулах ба энэ нь $i$ дахь хичээлийн дасгалын тооны хязгаар болон мөн $i$ дахь хичээлийн төвөгтэй байдлыг харуулна. Хичээлүүд нь $1$-ээс $m$ хүртэл дугаарлагдана.

C++ дахь 64 бит бүхэл тоог унших болох бичихдээ %lld нарийвчлал ашиглахгүйг анхаарна уу. Үүний оронд cout хэсгийг ашиглах нь зүйтэй (мөн %I64d$ ашиглаж болно).

Гаралт

Шийдэл олдохгүй бол "NO" гэж хэвлэнэ үү.

Өөр тохиолдолд, эхний мөр нь "YES" гэсэн үг агуулах ба дараагийн $n$ мөрүүд нь бүх нөхцлийг хангах ямар ч цагийн хуваарь агуулж болно. $i + 1$ мөр нь хоёр бүхэл тоо агуулах ба энэ нь $i$ дэх өдөр судлах хичээлийн болон энэхүү хичээлд өгөгдөх гэрийн даалгаварын тоог харуулна. Цагийн хуваарьт яг $n$ тооны хичээл багтана.

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

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

Оролт
4 5 2
1 10 1
1 10 2
1 10 3
1 20 4
1 100 5
Гаралт
YES
2 8
3 10
4 20
5 40
Оролт
3 4 3
1 3 1
2 4 4
2 3 3
2 2 2
Гаралт
NO
Сэтгэгдлүүдийг ачааллаж байна...