97D орчуулах · Codeforces.mn

# Хадгалах өрөөнд байгаа робот
Профессор гэрийнхээ роботыг дахиад алдчихжээ. Жоохон бодож зогссоны дараа Профессор хадгалах өрөндөө орхисноо санав.

Профессорын хадгалах өрөө нь $n × m$ хэмжээтэй $1 × 1$ нүднүүдээс бүрднэ. Зарим нүднүүд хана байх ба энэ нүдээр явах боломжгүй, бусад нүднүүдээр явж болно. Аль ч явж болдог нүднүүдээс бусад бүх явж болох нүдрүү аль нэг хөрш нүднүүдээрээ дамжин очиж болдог. Нүднүүдийн аль нэг нь хадгалах өрөөнөөс гарах гарц байна. Робот хадгалах өрөөнөөс гарах нүдэнд байрлаж болно.

Профессор харанхуй хадгалах өрөөнөөс роботоо хайхаас айж байв. Гэсэн хэдий ч профессорт хадгалах өрөөний газрын зураг болон роботын удирдлага байгаа. Удирдлагыг ашиглан роботыг зүүн, баруун, дээш, доош хөдөлгөж болно. Хэрэв хөдлөх гэж байгаа чиглэлийн хөрш нүд нь хана биш бол хөдөлж болно. Үгүй бол хөдөлгөөнгүй үлдэнэ.

Профессор цаасан дээр $k$ ширхэг үйлдэл бичсэн. Тэр энэхүү үйлдлүүд роботын хаана байхаас хамаарахгүйгээр хадгалах өрөөнөөс гарч чадна гэж бодож байгаа. Профессор роботдоо үйлдлүүдийг нь өгчихөөд унтах гэж байгаа.

Робот үйлдэл хийх болгонд тог зарцуулдаг ба Профессор сарын төгсгөлд хэтэрхий их тогны мөнгө төлөхийг хүсэхгүй байгаа. Ийм учраас таныг хамгийн багадаа цаасан дээр бичигдсэн үйлдлүүдийн эхний хэдэн үйлдлийг хийхэд дээрх дурьдсан нөхцлийг хангах вэ гэж асуусан юм.

## Оролт
Эхний мөрөнд $n$, $m$ ба $k$ ($3 ≤ n, m ≤ 150$, $1 ≤ k ≤ 10^{5}$) бүхэл тоонууд. Дараагийн $n$ мөрийн $m$ тэмдэгт бүрд - профессорын хадгалах өрөөний мэдээлэл байна: "#" хана, ".$" явж болох нүд ба "E$" гарц (энэ нүдээр явж болно). Аль ч нүднээс гарах хаалга хүртэл очиж болдог, $n × m$ тэгш өнцөгтийн хүрээ нь хана байна. Хадгалах өрөөнд ганцхан гарц байгаа. Сүүлийн мөрөнд $k$ урттай тэмдэгт мөр байна - Профессорын цаасан дээр бичсэн үйлдлүүд. "L$", "R$", "U$", "D$" харгалзан зүүн, баруун, дээд, доош гэсэн үйлдлийг төлөөлнө.

## Гаралт
Хариу болох хамгийн багадаа цаасан дээр бичигдсэн үйлдлүүдийн эхний хэдэн үйлдлийг хийхэд дээрх дурьдсан нөхцлийг хангах тоо байна. Хэрэв бүх $k$ үйлдлийг хийхэд дээрх нөхцлийг хангахгүй бол "-1" (хашилтгүйгээр) гэж  хэвлэнэ үү. Хэрэв хадгалах өрөөнд ганцхан явж болдог нүд байдаг ба тэр нь гарц байвал "0" (хашилтгүйгээр) гэж  хэвлэнэ үү.

-- Б.Алтангэрэл

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

Оролт

5 5 7
#####
#...#
#...#
#E..#
#####
UULLDDR

Гаралт

Оролт

5 5 7
#####
#.#.#
#...#
#E..#
#####
UULLDDR

Гаралт

-1

Оролт

5 3 2
###
#.#
#.#
#E#
###
DD