D. Эрдэнэсийн арал

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

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

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

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

Манай эрэлхэг аялагчид эрдэнэс нуусан арал дээр хүрчээ. Намган дундах усан онгоцоос ахмад жижиг хэсгийг нь харх идчихсэн эрдэнэс нуусан газрын газрын зургийг олжээ.

Газрын зураг $n × m$ хэмжээтэй тэгш өнцөгт хэлбэртэй ажээ. Нүд болгон арлын жижиг хэсгийг төлөөлнө (нүд хоорондын зай 1 милл). Зарим нүд нь далайтай шууд холбогдсон байдаг бөгөөд гатлаж чадахгүй. Бусад нүднүүдийг гаталж чадна. Жишээ нь, өндөр уулын мод, агуйн чулуу г.м.

Үүнээс гадна, газрын зураг $k$ ширхэг заавартай. Заавар болгон дараах хэлбэртэй : "$n$ милл $y$ зүгт алх"

Боломжит алхаж болох зүг нь хойд, урд, баруун, зүүн зүг юм. Хэрэв эдгээр зааврыг анхааралтай дагавал (бүгдийг нь нэг нэгээр нь заавал гүйцэтгэх ёстой.) эрдэнэс нуусан газарт яг очиж чадна.

Харамсалтай нь ахмад хаанаас эхлэхээ мэдэхгүй байгаа (жижиг хэсэг нь харханд идүүлчихсэн учир). Ахмад эхлэж болох хэдэн газрыг тэмдэглэсэн. Ямартай ч ахмад арлын хаагуур нь явах боломжтойг мэддэг.

Ахмад зааврын нөхцлийг хангадаг эхлэх цэгүүдийг мэдэхийг хүсэж байна. Түүнд туслана уу.

Оролт

Эхний мөрөнд $n$ болон $m$ ($3 ≤ n, m ≤ 1000$). Дараагийн $n$ мөр $m$ багана бүрд - газрын зургийн мэдээлэл. "#" далайг дүрслэнэ. Тэгш өнцөгтийн хүрээ нь далай байна. "." явж болох газар, шалгаж өгөх ёстой газрууд том латин үсгээр тэмлэглэгдэнэ. Бүх үсэг ашиглагдахгүй байж болно. Ядаж 1 шалгах ёстой газар байна. Бүх шалгах газрууд өөр үсгээр тэмдэглэгдсэн байна. Дараагийн мөрөнд $k$ ($1 ≤ k ≤ 10^{5}$), үүний дараагийн $k$ мөрөнд дээрх тайлбарласнаар өгөгдөнө. Заавар "$dir len$" гэсэн хэлбэртэй байна, $dir$ "N", "S", "W" ба "E" гэх утга авах бөгөөд харгалзан хойд, өмнөд, баруун, зүүн зүгийг заана. Хойд зүг дээшээ, өмнөд зүг доошоо, баруун зүг зүүн, зүүн зүг баруун талд байрлана. $len$ $1-ээс 1000$ хүртэлх утга авна.

Гаралт

Зааврын нөхцлийг хангадаг эхлэх цэгүүдийг цагаан толгойн дарааллаар хэвлэ. Хэрэв нөхцлийг хангах ганц ч цэг олдохгүй бол "no solution" (хашилтгүйгээр) гэж хэвлэ.

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

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

Оролт
6 10
##########
#K#..#####
#.#..##.##
#..L.#...#
###D###A.#
##########
4
N 2
S 1
E 1
W 2
Гаралт
AD
Оролт
3 4
####
#.A#
####
2
W 1
N 2
Гаралт
no solution
Сэтгэгдлүүдийг ачааллаж байна...