B. Филип ба Галт тэрэгнүүд

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

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

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

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

Гар утасны аппликейшний дэлгүүр "Метроны замаар өнхрөгч" нэртэй шинэ тоглоомтой болсон.

Тоглоомын гол дүр Филип тунелийн нэг төгсгөлд байрлах ба нөгөө төгсгөлрүү очихыг хүсч байна. Тунел нь гурван мөр, $n$ баганатай тэгш өнцөгт хэлбэртэй талбар байна. Тоглоомын эхэнд гол дүр хамгийн зүүн талын баганын аль нэг нүдэнд байна. Хэдэн ширхэг галт тэрэг гол дүрруу чиглэн хөдлөнө. Галт тэрэг бүр нэг мөрний хөрш хоёр болон түүнээс их нүднээс бүрдэнэ.

Бүх галт тэрэгнүүд баруунаас зүүн тийш секундэд хоёр нүдний хурдтай хөдлөх ба гол дүр зүүнээс баруун тийш секундэд нэг нүдний хурдтай хөдлөнө. Илүү хялбар байх үүднээс гол дүр ба галт тэрэгнүүд ээлжлэн хөдлөнө. Эхлээд гол дүр баруун тийш нэг нүд хөдлөх ба тэгээд дээшээ эсвэл доошоо нэг нүд явж болно эсвэл хөдлөхгүй байж болно. Тэгээд бүх галт тэрэгнүүд зүүн тийш нэг нүдээр хоёр удаа зэрэг хөдлөнө. Иймээс Филип нэг хөдлөхдөө баруун тийш гарцаагүй нэг нүд хөдлөх ба дээшээ эсвэл доошоо хөдлөж болно. Ямар ч үед хэрвээ Филип галт тэрэгтэй нэг нүдэнд байвал тэр хожигдоно. Хэрвээ галт тэрэг зүүн баганад хүрвэл тунелийг өнгөрөөд цаашаа хөдлөсөөр байна.

Таны ажил бол Филипд хамгийн баруун баганад хүрэх боломжтой хөдөлгөөний дараалал байгаа юу гэсэн асуултад хариу өгөх явдал юм.

Оролт

Тест бүр оролтын өгөгдлийн нэгээс арав хүртэлх бүрдэл агуулна. Тестийн эхний мөрөнд нэг ширхэг бүхэл тоон утга $t$ (урьдчилсан тестүүд болон тестүүдийн хувьд $1 ≤ t ≤ 10$ ба халдлагын хувьд $t = 1$ байна; дэлгэрэнгүйг Тэмдэглэл хэсгээс харна уу) байх ба бүрдлүүдийн тоо байна.

Тэгээд оролтын өгөгдлийн $t$ бүрдлийн тайлбар байна.

Бүрдэл бүрийн тайлбарын эхний мөрөнд хоёр бүхэл тоон утга $n, k$ ($2 ≤ n ≤ 100, 1 ≤ k ≤ 26$) байх ба талбарын баганын тоо ба галт тэрэгнүүдийн тоо байна. Дараагийн гурван мөрийн мөр бүрт $n$ тэмдэгтийн дараалал байх ба тоглоом явагдах талбарын мөрийг илтгэнэ. Филипийн анхны байрлал '$s$'-р тэмдэглэгдэх ба тэр хамгийн зүүн баганад байна. $k$ галт тэрэгнүүдийн нэг бүр нь Англи цагаан толгойн ижил том үсгээс бүрдэх дарааллаар тэмдэглэгдэх ба нэг мөрөнд л байна. Ялгаатай галт тэрэгнүүд ялгаатай үсгээр тэмдэглэгдэнэ. '$.$' тэмдэгт нь хоосон нүдийг илтгэх буюу уг нүд Филип болон галт тэрэгний аль алийг нь агуулаагүй гэсэн үг.

Гаралт

Хэрвээ оролтын өгөгдлийн бүрдэл бүрийн хувьд тоглоомонд хожих боломжтой бол $YES$ үгийг нэг мөрөнд хэвлэх ба бусад тохиолдолд $NO$ үгийг хэвлэнэ.

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

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

Оролт
2
16 4
...AAAAA........
s.BBB......CCCCC
........DDDDD...
16 4
...AAAAA........
s.BBB....CCCCC..
.......DDDDD....
Гаралт
YES
NO
Оролт
2
10 4
s.ZZ......
.....AAABB
.YYYYYY...
10 4
s.ZZ......
....AAAABB
.YYYYYY...
Гаралт
YES
NO

Тэмдэглэл

Эхний жишээний эхний оролтын өгөгдлийн бүрдлийн хувьд Филип эхлээд урагшаа явах ба талбарын гурав дахь мөррүү доошоо явна, тэгээд зөвхөн урагшаа явна, тэгээд урагшаа яваад хоёр дахь мөррүү дээшлэнэ, дахиад урагшлах ба нэгдүгээр мөррүү дээшлэнэ. Үүний дараа Филипийн замд ямар галт тэрэгний блок байхгүй болох ба тэр тунелийн эцэс хүртэл шулуун явж болно.

Энэ бодлогон дээр зөвхөн нэг тестийн бүрдэл агуулсан тестүүдийг турших нь хязгаарлагдсан.

Сэтгэгдлүүдийг ачааллаж байна...