J. Бомбтой баатар

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

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

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

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

Нэгэн шинэ компьютер тоглоомонд та $n × m$ хэмжээтэй тэгш өнцөгт хавтан бүхий оньсноос гарахад нь тоглоомын баатарт туслах хэрэгтэй. Баатар талбарын нүднүүдийн аль нэгэнд байрлана. Тэр оньсны гарцыг мэдэж байгаа ба тэнд хүрэхийг хүсч байна.

Нэг үйлдэлд баатар хэрвээ хажуу талын нүд (өөрөөр уг нүдтэй нэг талтай нүд) нь хоосон байвал тийшээ нүүж болно эсвэл байгаа нүдэндээ бомб тавьж болно эсвэл үйлдлээ алгасаад юу ч хийхгүй байж болно. Бомб гурван нүүдлийн дараа дэлбэрэх буюу баатар дахиад гурван үйлдэл хийсний дараа боловч дөрөв дэх үйлдлээ хийхээс өмнө гэсэн үг (дээр тодорхойлогдсон гурван төрлийн нүүдэл нь бүгд үйлдэл гэж тоологдоно).

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

Таны ажил бол гарцад хүрэхэд баатрын хийх үйлдлүүдийн дарааллыг тодорхойлох юм. Та дарааллын уртыг хамгийн бага байлгах шаардлагагүй. Байгаа ганц хязгаарлалт нь дарааллын урт 100,000 тэмдэгтээс хэтрэхгүй байх ёстой.

Оролт

Эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ ($1 ≤ n, m ≤ 100$, $n*m > 1$) байх буюу оньсны хэмжээ юм.

Дараагийн $n$ мөр бүрт $m$ тэмдэгт байх буюу оньсны тайлбар юм. Энд "$.$" нь хоосон нүд, "$E$" нь баатар, "$T$" нь гарц бол "$X$" нь бартаа юм.

Мөн оньсонд яг нэг баатар болон нэг гарц байх нь тодорхой.

Гаралт

Баатрын оньсноос гарах үйлдлүүдийг хэвлэ (энд "$M$" нь бомб тавих, "$T$" нь үйлдлээ алгасах, "$S$" нь доош явах, "$W$" нь зүүн тийш явах, "$N$" нь дээш явах, "$E$" нь баруун тийш явах). Хэрвээ баатар гарцад хүрэх боломжгүй бол "$No solution$" (хашилтгүйгээр) гэж хэвлэ.

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

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

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

Оролт
3 5
XEX.X
X.XXT
X.X.X
Гаралт
SSMNNTSSNEMWWTEEEE
Сэтгэгдлүүдийг ачааллаж байна...