E. Принтер

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

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

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

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

Сүлжээний принтер дараах байдлаар ажиллана. Принтер хугацааны $0$ агшинд ажиллаж эхлэх ба секунд бүрт нэг хуудас хэвлэх чадвартай. Хугацааны аль нэг агшинд принтер комманд авна. Бид принтер $n$ комманд хүлээж авахыг мэдэж байгаа. Коммандуудыг $1$-ээс $n$ хүртэл дугаарлая. $i$-дэх команд хугацааны $t_{i}$ агшинд өгөгдөн $s_{i}$ хуудас хэвлэхийг хүсэх ба $p_{i}$ гэсэн Ач Холбогдлын Коэффициенттэй байна. Бүх ач холбогдлын коэффициентүүд ялгаатай.

Принтер коммандыг хүлээн авах үед комманд нь хүлээлгийн дараалалд орох ба түүний бүх хуудас хэвлэгдэж дуустал хүлээлгийн дараалалдаа байх болно. Принтер хэвлэх хуудсаа ямар нэг хуудас хэвлэж дуусаад эсвэл шинэ комманд хүлээн авахдаа сонгох болно. Сонгохдоо хамгийн их ач холбогдлын коэффициенттэй команд дахь хэвлэгдээгүй хуудсыг сонгох болно. Комманд агшин зуурын дотор өгөгдөх тул комманд $t$ агшинд дөнгөж ирсэн ч принтер түүнийг сонгох боломжтой юм.

Чамд нэг коммандын мэдээллээс бусад нь өгөгдөнө: тэрхүү коммандын ач холбогдлын коэффициентийг мэдэхгүй боловч энэ коммандын хамгийн сүүлийн хуудас хэвлэгдэж дууссан агшинг мэднэ. Энэ мэдээллүүд өгөгдсөнөөр үл мэдэгдэх ач холбогдлын коэффициент ба комманд бүрийн хэвлэгдэж дуусах агшнуудыг олно уу.

Оролт

Эхний мөрөнд бүхэл тоо $n$ ($1 ≤ n ≤ 50000$) байна. Дараагийн $n$ мөрөнд коммандуудыг тодорхойлно. $i$-дэх мөрөнд $t_{i}$, $s_{i}$, $p_{i}$ тоонууд зайгаар тусгаарлагдан байна. Яг нэг мөрөн дэх ($x$ дэх мөр гэж үзье) ач холбогдлын коэффициентийн оронд "-1" байх болно. Бүх ач холбогдлын коэффициентүүд ялгаатай. Сүүлчийн мөрөнд $x$ ($1 ≤ T ≤ 10^{15}$) дэх коммандын сүүлийн хуудас хэвлэгдэж дуусах хугацаа болох $T$ бүхэл тоо байна. $t_{i}$-үүд ялгаатай байх албагүй. Өгөгдөлд коммандуудын дараалал дурын дарааллаар өгөгдөх болно.

Гаралт

Эхний мөрөнд үл мэдэгдэх ач холбогдлын коэффициент $p_{x}$-ииг хэвлэ. Бүх ач холбогдлын коэффициентүүд ялгаатай гэдгийг санаарай. Дараа нь $n$ ширхэг бүхэл тоо хэвлэнэ. $i$-дэх тоо нь $i$-дэх коммандын сүүлийн хуудас хэвлэгдэж дуусах хугацаа байхаар хэвлэнэ.

Ядаж нэг хариу байдаг байхаар өгөгдөнө. Олон хувилбар байвал аль нэгийг нь л хэвлээрэй.

Орчуулсан: Бат-Од

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

Оролт
3
4 3 -1
0 2 2
1 3 3
7
Гаралт
4
7 8 4
Оролт
3
3 1 2
2 3 3
3 1 -1
4
Гаралт
4
7 6 4

Тэмдэглэл

Эхний жишээг авч үзье. Үл мэдэгдэх ач холбогдлын коэффициент нь $4$ гэж үзье. Тэгвэл принтерийн секунд бүрт хийх үйлдлүүд дараах байдалтай байна:

  • $1$-р секундийн эхэнд ($0$ агшинд). Хүлээлгийн дараалалд $2$-р комманд байна. Принтер энэ коммандын эхний хуудсыг хэвлэнэ;
  • $2$-р секундийн эхэнд ($1$ агшинд). Хүлээлгийн дараалалд $2$, $3$-р коммандууд байна. Принтер $3$-р коммандын эхний хуудсыг хэвлэнэ;
  • $3$-р секундийн эхэнд ($2$ агшинд). Хүлээлгийн дараалалд $2$, $3$-р коммандууд байна. Принтер $3$-р коммандын хуудсыг хэвлэнэ;
  • $4$-р секундийн эхэнд ($3$ агшинд). Хүлээлгийн дараалалд $2$, $3$-р коммандууд байна. Принтер $3$-р коммандын сүүлийн хуудсыг хэвлэнэ. Тиймээс $3$-р коммандын сүүлийн хуудас $4$-р секунд дуусах үед хэвлэгдэж дууссан байна;
  • $5$-р секундийн эхэнд ($4$ агшинд). Хүлээлгийн дараалалд $2$, $1$-р коммандууд байна. Принтер $1$-р коммандын эхний хуудсыг хэвлэнэ;
  • $6$-р секундийн эхэнд ($5$ агшинд). Хүлээлгийн дараалалд $2$, $1$-р коммандууд байна. Принтер $1$-р коммандын хуудсыг хэвлэнэ;
  • $7$-р секундийн эхэнд ($6$ агшинд). Хүлээлгийн дараалалд $2$, $1$-р коммандууд байна. Принтер $1$-р коммандын сүүлийн хуудсыг хэвлэнэ. Тиймээс $7$-р секунд дуусах үед $1$-р коммандын сүүлийн хуудас хэвлэгдэж дуусна;
  • $8$-р секундийн эхэнд ($7$ агшинд). Хүлээлгийн дараалалд $2$-р комманд байна. Принтер $2$-р коммандын сүүлийн хуудсыг хэвлэнэ. Тиймээс $8$-р секүнд дуусах үед $2$-р коммандын сүүлийн хуудас хэвлэгдэж дуусна.

Нөхцөлд шаардсан ёсоор $1$-р комманд $7$-р секүндийг дуусах үед хэвлэгдэж дууссан. Мөн $2$ ба $3$-р коммандууд харгалзан $8$ ба $4$-р секунд дуусах үед хэвлэгдэж дуусна.

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