E. Цахилгаан шат

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

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

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

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

Олон улсын КодФорсес корпорацийн $m$ давхар $(m > 1)$ оффис дэвшилтэт цахилгаан шат удирдах системтэй. Уг систем нь дараах байдлаар ажилладаг.

Оффисийн давхаруудыг 1-с $m$ хүртэл бүхэл тоогоор дугаарласан. Хугацааны $t = 0$ агшинд цахилгаан шат нэг давхарт байх ба хоосон байна мөн бусад давхруудад нэг ч хүн хүлээгээгүй байна. Дараа нь хугацааны $t_{i}$ $(t_{i} > 0)$ мөчүүдэд хүмүүс цахилгаан шат дээр ирнэ. Илүү хялбар болгох үүднээс тодорхойлогдсон хугацааны туршид нэг хүн цахилгаан шатыг нэг л удаа ашиглана. Хүн бүрийн хувьд бид гурван параметрийг мэдэж байгаа: эхнийх нь тухайн хүний цахилгаан шатан дээр ирэх цаг, тухайн хүний анх байсан давхар болон очихыг хүсч буй давхар байна.

Цахилгаан шат давхар хооронд дараах байдлаар явна. Хугацааны $t$ ($t ≥ 0$, $t$ бүхэл тоо) агшинд цахилгаан шат үргэлж аль нэг давхарт байна. Эхлээд цахилгаан шат дотор байгаа хүмүүсийн буух давхрыг тодорхойлж одоо байгаа давхарт буухыг хүсч байгаа хүмүүсийг суллана. Тэгээд уг давхарт байгаа цахилгаан шат хүлээж буй хүмүүсийг орохыг зөвшөөрнө. Хэрвээ хэн нэгэн хугацааны яг $t$ агшинд цахилгаан шатан дээр ирсэн бол тэр хүн сууж амжина. Бид цахилгаан шатанд суух болон буух үйлдлүүд нь маш хурдан хийгдэнэ гэж үзнэ. Үүний дараа цахилгаан шат хаашаа явахаа шийдэх ба сонгосон давхартаа хугацааны $(t + 1)$ агшинд очно.

Цахилгаан шат явах чиглэлээ дараах алгоритмаар шийднэ.

  • Хэрвээ цахилгаан шат хоосон, мөн тухайн агшинд аль ч давхарт хэн ч цахилгаан шат хүлээгээгүй бол цахилгаан шат одоо байгаа давхартаа үлдэнэ.
  • Бусад тохиолдолд, цахилгаан шатыг $x$ $(1 ≤ x ≤ m)$ давхарт байна гэе. Ингээд цахилгаан шат "зэрэглэл" $p_{up}$ ба $p_{down}$ чиглэлээ тооцоолно. $p_{up}$ бол $x$-с их дугаартай давхруудад цахилгаан шат хүлээж байгаа хүмүүсийн тоо болон $x$-с их дугаартай давхруудад буух хүсэлтэй цахилгаан шатанд байгаа хүмүүсийн тооны нийлбэр байна; $p_{down}$ бол $x$-с бага дугаартай давхруудад цахилгаан шат хүлээж байгаа хүмүүсийн тоо болон $x$-с бага дугаартай давхруудад буух хүсэлтэй цахилгаан шатанд байгаа хүмүүсийн тооны нийлбэр байна. Хэрвээ $p_{up} ≥ p_{down}$ байвал цахилгаан шат нэг давхар дээшээ ($x$-с $x + 1$ давхарруу) явна, бусад тохиолдолд цахилгаан шат нэг давхар доошоо ($x$-c $x - 1$) явна.

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

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоо $n, m (1 ≤ n ≤ 10^{5}, 2 ≤ m ≤ 10^{5})$ байх буюу харгалзан барилга дахь хүмүүс болон давхрын тоо байна.

Дараагийн $n$ мөр бүрт зайгаар тусгаарласан гурван бүхэл тоо $t_{i}, s_{i}, f_{i} (1 ≤ t_{i} ≤ 10^{9}, 1 ≤ s_{i}, f_{i} ≤ m, s_{i} ≠ f_{i})$ байх ба $i$-р хүн цахилгаан шат хүлээж эхэлсэн цаг, $i$-р хүний анх байрлаж байсан давхрын дугаар болон очихыг хүсч буй давхрын дугаар байна.

Гаралт

$i$-р мөрөнд $i$-р хүн хэрэгтэй давхартаа очих цагийг илэрхийлэх $n$ мөр хэвлэ. Хүмүүс оролтонд өгсөн дарааллаараа дугаарлагдсан.

C++ хэлэнд 64 битийн бүхэл тонуудыг унших болон бичихдээ $\%lld$ тодорхойлогчийг битгий ашиглаарай. $cin$, $cout$ урсгалууд болон $\%I64d$ тодорхойлогчийг ашиглаарай.

Орчуулсан: Г.Мэндбаяр

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

Оролт
3 10
1 2 7
3 6 5
3 4 8
Гаралт
7
11
8
Оролт
2 10
1 2 5
7 4 5
Гаралт
5
9

Тэмдэглэл

Эхний жишээн дээр цахилгаан шат дараах байдалтай ажиллана:

  • $t = 1$. Цахилгаан шат $1$ давхарт байна. Цахилгаан шат хоосон. $2$ давхарт нэг хүн хүлээж байна. $p_{up} = 1 + 0 = 1, p_{down} = 0 + 0 = 0, p_{up} ≥ p_{down}$. Цахилгаан шат $2$ давхарруу явна.
  • $t = 2$. Цахилгаан шат $2$ давхарт байна. Цахилгаан шатанд нэг хүн суух ба $7$ давхарт гарахыг хүсч байна. $p_{up} = 0 + 1 = 1, p_{down} = 0 + 0 = 0, p_{up} ≥ p_{down}$. Цахилгаан шат $3$ давхарруу явна.
  • $t = 3$. Цахилгаан шат $3$ давхарт байна. Цахилгаан шатанд нэг хүн байгаа ба $7$ давхарт гарахыг хүсч байна. $4$ болон $6$ давхарт нийт хоёр хүн хүлээж байна. $p_{up} = 2 + 1 = 3, p_{down} = 0 + 0 = 0, p_{up} ≥ p_{down}$. Цахилгаан шат $4$ давхарруу явна.
  • $t = 4$. Цахилгаан шат $4$ давхарт байна. Цахилгаан шатанд нэг хүн байгаа ба $7$ давхарт гарахыг хүсч байна. Цахилгаан шатанд нэг хүн суух ба $8$ давхарт буухыг хүсч байна. $6$ давхарт нэг хүн хүлээж байгаа. $p_{up} = 1 + 2 = 3, p_{down} = 0 + 0 = 0, p_{up} ≥ p_{down}$. Ингээд цахилгаан шат $5$ давхарруу явна.
  • $t = 5$. Цахилгаан шат $5$ давхарт байна. Цахилгаан шатанд хоёр хүн байгаа ба $7$ ба $8$ давхарт буухыг хүсч байна. $6$ давхарт нэг хүн хүлээж байгаа. $p_{up} = 1 + 2 = 3, p_{down} = 0 + 0 = 0, p_{up} ≥ p_{down}$. Ингээд цахилгаан шат $6$ давхарруу явна.
  • $t = 6$. Цахилгаан шат $6$ давхарт байна. Цахилгаан шатанд хоёр хүн байгаа ба $7$ ба $8$ давхарт буухыг хүсч байна. Цахилгаан шатанд нэг хүн орж ирэх ба $5$ давхарт буухыг хүсч байна. $p_{up} = 0 + 2 = 2, p_{down} = 0 + 1 = 1, p_{up} ≥ p_{down}$. Ингээд цахилгаан шат $7$ давхарруу явна.
  • $t = 7$. Цахилгаан шат $7$ давхарт байна. $7$ давхарт буухыг хүссэн нэг хүн бууна. Цахилгаан шатанд хоёр хүн байгаа ба $8$ ба $5$ давхарт буухыг хүсч байна. $p_{up} = 0 + 1 = 1, p_{down} = 0 + 1 = 1, p_{up} ≥ p_{down}$. Ингээд цахилгаан шат $8$ давхарруу явна.
  • $t = 8$. Цахилгаан шат $8$ давхарт байна. $8$ давхарт буухыг хүссэн нэг хүн бууна. Цахилгаан шатанд $5$ давхарт буух хүсэлтэй нэг хүн байна. $p_{up} = 0 + 0 = 0, p_{down} = 0 + 1 = 1, p_{up} < p_{down}$. Ингээд цахилгаан шат $7$ давхарруу явна.
  • $t = 9$. Цахилгаан шат $7$ давхарт байна. Цахилгаан шатанд $5$ давхарт буух хүсэлтэй нэг хүн байна. $p_{up} = 0 + 0 = 0, p_{down} = 0 + 1 = 1, p_{up} < p_{down}$. Ингээд цахилгаан шат $6$ давхарруу явна.
  • $t = 10$. Цахилгаан шат $6$ давхарт байна. Цахилгаан шатанд $5$ давхарт буух хүсэлтэй нэг хүн байна. $p_{up} = 0 + 0 = 0, p_{down} = 0 + 1 = 1, p_{up} < p_{down}$. Ингээд цахилгаан шат $5$ давхарруу явна.
  • $t = 11$. Цахилгаан шат $5$ давхарт байна. Цахилгаан шатнаас анх $5$ давхарт буух хүсэлтэй орж ирсэн нэг хүн бууна. Цахилгаан шат хоосон мөн өөр хүн дуудаагүй учраас $5$ давхартаа үлдэнэ.
Сэтгэгдлүүдийг ачааллаж байна...