A. Лифт

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

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

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

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

Саяхан маш их оролцогчтой, маш их нэрт хүндтэй тэмцээнүүдийн нэг болох Russian Code Cup амжилттай өндөрлөлөө. Бүх $n$ финалд шалгарсан оролцогчид аварга $m$-давхар $10^{8}$-одтой зочид буудалд буудаллажээ. Мэдээж хамгийн түрүүн орж ирээд "Лифтийг нь сонирхвол яасан юм?" гэж бодогдоно.

Зочид буудлын лифт хэзээж өөрчлөгдөхгүй дарааллаар хөдөлдөг. Анх (0-р мөчид) лифт 1-р давхарт байгаа, дараа нь 2-р давхар луу, г.м $m$-р давхарт очоод, $m-1$-р давхар луу, г.м 1-р давхарт ирнэ. Энэ дараалал хязгааргүй үргэлжлэх ба лифт хязгааргүй багтаамжтай. Хүмүүс очих ёстой буудал дээрээ ирчхээд илүү цаг авалгүй шууд буудаг. Давхар хооронд шилжихэд нэгж хугацаа зарцуулдаг.

$n$ оролцогчдын хувьд таньд $s_{i}$, $i$-р оролцогчийн гарч ирсэн давхар, $f_{i}$, $i$-р оролцогчийн очхыг хүссэн газар, $t_{i}$, $i$-р оролцогчийн $s_{i}$ давхарт гарч ирсэн хугацаа.

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

Хэрэв лифт $s_{i}$ давхарт $t_{i}$ хугацаанд гарч ирэхэд шууд лифтэнд сууна. Хэрэв буух буудал нь эхлэлийн буудалтайгаа ижилхэн бол ($s_{i} = f_{i}$), $f_{i}$ буудал дээр ирэх хугацаа нь $t_{i}$ болно.

Оролт

Эхний мөр $n$ and $m$ ($1 ≤ n ≤ 10^{5}, 2 ≤ m ≤ 10^{8}$) бүхэл тоо байна.

Дараагийн $n$ мөрд оролцогчдын мэдээлэл болох $s_{i}$ $f_{i}$ $t_{i}$ ($1 ≤ s_{i}, f_{i} ≤ m, 0 ≤ t_{i} ≤ 10^{8}$), бүхэл тоонууд байна.

Гаралт

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

Орчуулсан: Б.Алтангэрэл

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

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

Тэмдэглэл

Эхний жишээг ажиглая. Эхний оролцогч $s = 2$ давхарт $t = 3$ болоход гарч ирнэ. $f = 4$ давхарт очиход тэр дахиад цаг $7$ болох хүртэл хүлээх ёстой. Энэ нь лифтийг хоёрдахь удаагаа дээшээ явах хугацаа юм. Тэгээд эхний оролцогч лифтэнд суугаад хоёр давхар дээшээ явна. Энэ жишээнд цаг $9$ болоход $f$ давхарт очно. Хоёрдах оролцогч $t = 0$ хугацаанд $s = 1$ давхраас лифтэнд суугаад $f = 2$ давхарт очно. Гуравдахь оролцогч лифт хүлээх шаардлагагүй, учир нь тэр эхлэх давхартаа очих ёстой учраас.

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