B. Шениа ба Тагнуулууд

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

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

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

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

Чадварлаг мөрдөгч Шениа нэг мөрөнд зогссон гадаадын $n$ $(n ≥ 2)$ тагнуултай тулгарсан. Бид тагнуулуудыг зүүнээс баруун тийш 1-c $n$ хүртэл дугаарлагдсан гэж үзнэ.

$s$ тагнуулд чухал тэмдэглэл байгаа. Тэр энэ тэмдэглэлийг $f$ тагнуулд дамжуулах хэрэгтэй. Шениа тагнуулуудыг хэд хэдэн алхмуудаар байцаадаг. Нэг алхмын үед чухал тэмдэглэлийг хадгалж байгаа тагнуул хөрш тагнуулдаа тэмдэглэлийг дамжуулж чадна. Өөрөөр хэлбэл хэрвээ тагнуулын дугаар $x$ байвал уг тагнуул тэмдэглэлийг $x - 1$ эсвэл $x + 1$ дугаартай тагнуулд дамжуулж чадна (хэрвээ тагнуулын $x = 1$ эсвэл $x = n$ байвал нэг хөрштэй байна). Мөн нэг алхмын үед тагнуул тэмдэглэлээ хэнд ч дамжуулахгүй өөртөө авч үлдэж болно.

Гэхдээ бүх зүйл ийм хялбар биш. $m$ алхмын турш Шениа зарим тагнуулыг анхааралтай ажиглана. Ялангуяа $t_{i}$ (алхмуудыг 1-с эхлэн дугаарлана) алхмын үед Шениа $l_{i}, l_{i} + 1, l_{i} + 2, ..., r_{i}$ $(1 ≤ l_{i} ≤ r_{i} ≤ n)$ дугаартай тагнуулуудыг ажиглана. Мэдээж ямар нэг алхмын үед хэрвээ Шениа тухайн тагнуулыг ажиглаж байвал тагнуул юу ч хийж чадахгүй буюу тэмдэглэл дамжуулж мөн хүлээн авч чадахгүй. Бусад тохиолдолд Шениа тагнуулуудын зальжин хуйвалдааныг илрүүлнэ. Хэрвээ тагнуул тухайн алхамд тэмдэглэлийг өөртөө хадгалах юм бол Шениа түүнийг ажиглаж байсан ч ямар нэг сэжигтэй зүйл харж чадахгүй.

Танд $s$ ба $f$ байгаа. Мөн Шениагийн тагнуулуудыг ажиглах алхмууд болон алхам бүрийн хувьд аль тагнуулуудыг ажиглах вэ гэдгийг ч мэдэж байгаа. Тагнуулууд $s$ тагнуулаас $f$ тагнуул хүртэл тэмдэглэлийг дамжуулах хамгийн сайн арга буюу хамгийн хурдан аргыг (хамгийн цөөн алхамд) олно уу.

Оролт

Эхний мөрөнд дөрвөн бүхэл тоо $n$, $m$, $s$ ба $f$ $(1 ≤ n, m ≤ 10^{5}; 1 ≤ s, f ≤ n; s ≠ f; n ≥ 2)$ байна. Дараагийн $m$ мөр бүрт гурван бүхэл тоо $t_{i}, l_{i}, r_{i}$ $(1 ≤ t_{i} ≤ 10^{9}, 1 ≤ l_{i} ≤ r_{i} ≤ n)$ байна. $t_{1} < t_{2} < t_{3} < ... < t_{m}$ байх нь тодорхой.

Гаралт

Нэг мөрөнд $i$-р тэмдэгт нь $i$-р алхамд тагнуулуудын хийх үйлдлийг илэрхийлсэн $k$ тэмдэгт хэвлэнэ. Хэрвээ $i$-р алхамд тэмдэглэлтэй тагнуул тэмдэглэлээ бага дугаартай тагнуулруу дамжуулах ёстой бол $i$-р тэмдэгт нь "$L$" байна. Хэрвээ $i$-р алхамд тэмдэглэлтэй тагнуул тэмдэглэлээ их дугаартай тагнуулруу дамжуулах ёстой бол $i$-р тэмдэгт нь "$R$" байна. Хэрвээ $i$-р алхамд тэмдэглэлтэй тагнуул тэмдэглэлээ өөр дээрээ хадгалах ёстой бол $i$-р тэмдэгт нь "$X$" байна.

Хэвлэсэн үйлдлүүдийг гүйцэтгэсний үр дүнд $s$ тагнуул тэмдэглэлээ $f$ тагнуулд дамжуулсан байх ёстой. Хэвлэсэн тэмдэгтүүдийн тоо $k$ нь боломжит хамгийн бага байх ёстой. Шениа тэмдэглэл дамжуулж байгаа тагнуулуудыг барих ёсгүй.

Хэрвээ тохиромжтой хэд хэдэн шийдэл байвал алийг нь ч хэвлэж болно. Хариулт оршин байх нь тодорхой.

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

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

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