D. Шаасс ба будагч робот

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

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

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

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

Шаасс гал тогооны шал тэр чигээрээ цагаан байх нь уйтгартай юм гэж бодсон. Түүний гал тогооны шал $n × m$ хэмжээтэй тэгш өнцөгт бүхий $n*m$ дөрвөлжин хавтангаас бүрдэнэ. Иймээс тэр шалыг шатрын хөлөг шиг харагдахаар буюу ямар ч хоёр хөрш хавтан ялгаатай өнгөтэй байхаар шалны зарим хавтанг будахаар шийдсэн.

Шаасс хавтангуудыг будахдаа будагч робот ашиглахыг хүссэн. Эхлээд робот захын $(x_{s}, y_{s})$ хавтан дээр зогсож байгаа ба диагональ зүгрүү харж байна (өөрөөр хэлбэл зүүн дээшээ, баруун дээшээ, зүүн доошоо, баруун доошоо). Робот гал тогоонд явахдаа дайран гарсан бүх хавтангаа будах буюу будагдсан хавтан байсан ч давхарлан будна. Нэг хавтан будахад нэг нэгж хар будаг хэрэглэнэ. Дурын мөчид робот хэрвээ гал тогооны хана мөргөвөл чиглэлээ тушаалын дагуу өөрчилнө. Робот өөр хавтангаас уг хавтанд орж ирэхдээ хавтанг будах ба өөрөөр хэлбэл нэг хавтан дээрээ чиглэлээ өөрчлөхөд дахин будахгүй. Роботын зогсож буй эхний хавтан ч мөн будагдсан байна.

Робот шал шатрын хөлөг шиг болох мөчид зогсоно. Гал тогооны хэмжээ болон роботын байрлал өгөгдсөн бол робот шал будахаа зогсоох хүртэл хэрэглэх будагны хэмжээг ол.

Доор дүрслэсэн жишээг авч үзье.

Хэрвээ робот зүүн хүснэгтийн 1 дугаартай хавтангаас эхлэсэн ба баруун доош чиглэсэн бол 6 дугаартай хавтан дээр зогсох хүртэлээ 1354236 хавтангуудаар дайрах ба 7 нэгж хар будаг хэрэглэнэ. Харин хэрвээ робот баруун хүснэгтийн 1 дугаартай хавтангаас эхлэсэн ба баруун доош чиглэсэн бол 1, 2, 3 гэсэн хавтангуудыг будах давталтанд гацна.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоо $n$ ба $m$, $(2 ≤ n, m ≤ 10^{5})$ байна. Хоёр дахь мөрөнд хоёр бүхэл тоо $x_{s}$ ба $y_{s}$ $(1 ≤ x_{s} ≤ n, 1 ≤ y_{s} ≤ m)$ болон роботын харж буй чиглэл байна. Чиглэл нь дараах тэмдэгт мөрүүдийн аль нэг нь байна: "$UL$" (зүүн дээшээ), "$UR$" (баруун дээшээ), "$DL$" (зүүн доошоо) эсвэл "$DR$" (баруун доошоо).

$(x_{s}, y_{s})$ нь гал тогооны дээрээсээ $x_{s}$-р мөр болон зүүнээсээ $y_{s}$-р баганад байрласан хавтанг илэрхийлнэ.

Эхлэх байрлал нь үргэлж захын хавтан байна.

Гаралт

Робот шатрын хөлөг шиг гал тогооны шалтай болоход хэрэгтэй будгийн хэмжээг хэвлэ. Хэрвээ ийм зүйл болохгүй бол $-1$-г хэвлэ.

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

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

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

Оролт
3 4
1 1 DR
Гаралт
7
Оролт
3 4
3 3 DR
Гаралт
11
Оролт
3 3
1 1 DR
Гаралт
-1
Оролт
3 3
1 2 DL
Гаралт
4
Сэтгэгдлүүдийг ачааллаж байна...