C. Шилэн бөмбөгүүд

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

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

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

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

Баярын өдрөөр Сайтама Женос-д $n$ урттай хоёр хүснэгтэн зам өгсөн (хачин бэлэг ч гэсэн энэ бол Сайтамагийн стандарт). Хүснэгтэн зам нь хязгааргүй хүснэгтэн дээрх хөрш квадратуудын дараалласан дараалал юм. Нэг талтай хоёр квадрат нь хөрш болно.

Хүснэгтэн замын нэг жишээ нь $(0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (1, 1) -> (0, 1) -> ( - 1, 1)$ юм. Энэ дараалал дахь квадратууд нь давтагдаж болно, өөрөөр зам өөртэйгөө огтлолцож болно.

Хүснэгтэн зам дээрх хөдөлгөөн нь дараалал дахь хөрш квадратуудаар хязгаарлагдана. Энэ нь $i$-р квадратаас зөвхөн тухайн замын $(i - 1)$-р эсвэл $(i + 1)$-р квадратруу л хөдлөж болно гэсэн үг. Хүснэгтэн замын эхний болон эцсийн квадратаас боломжит ганцхан л хөдөлгөөн байгааг сана. Мөн зөвхөн $(i - 1)$-р болон $(i + 1)$-р квадратруу л хөдлөдөг $i$-р квадраттай давхцах $j$ квадрат байсан ч адилхан. Жишээлбэл дээр байгаа дарааллын хоёр дахь квадратаас зөвхөн нэг болон гурав дахь квадратруу л хөдлөж болно.

Хөдөлгөөнийг хоёрдмол биш байлгахын тулд хоёр хүснэгтэн зам нь гурван квадратын ээлжилсэн дараалал агуулахгүй. Жишээлбэл хүчинтэй хүснэгтэн замд $(0, 0) -> (0, 1) -> (0, 0)$ зэрэгцээ дэд дараалал оршихгүй.

Хүснэгтэн зам бүрийн эхний квадратад нэг шилэн бөмбөг байрласан. Женос хоёр бөмбөгийг хоёуланг нь хүснэгтэн зам бүрийн сүүлийн квадратад аваачихыг хүсэж байна. Гэхдээ энд бас нэг оньс байгаа нь Женос нэг бөмбөгийг хөдөлгөх үед нөгөө бөмбөг нь боломжтой бол энэ бөмбөгийн хөдөлгөөнийг хуулбарлана. Жишээлбэл хэрвээ нэг бөмбөг зүүн зүг хөдлөвөл нөгөө бөмбөг нь зүүн зүг хөдлөхийг эрмэлзэнэ. Эрмэлзэнэ гэдэг нь хэрвээ зүүн тийшээ явах нь хүчинтэй үйлдэл байвал шилэн бөмбөг зүүн тийшээ хөдлөнө гэсэн үг.

Хойд зүгт хөдлөх нь хоёр дахь координатыг $1$-р нэмэгдүүлэх бол урд зүгт хөдлөх нь $1$-р хорогдуулна. Үүнтэй адилаар зүүн зүгт хөдлөх нь эхний координатыг $1$-р нэмэгдүүлэх бол баруун зүгт хөдлөх нь эхний координатыг нэгээр багасгана.

Өгөгдсөн хоёр хүчинтэй хүснэгтэн замуудын хувьд Женос хоёр бөмбөгийг харгалзах замуудын төгсгөлрүү аваачиж болох эсэхийг мэдэхийг хүсч байна. Энэ нь хоёр бөмбөлөг хоёулаа харгалзах замын сүүлийн квадрат дээр очих боломжтой юу гэсэн үг.

Оролт

Оролтын эхний мөрөнд бүхэл тоон утга $n$ ($2 ≤ n ≤ 1 000 000$) байх буюу замуудын урт юм.

Оролтын хоёр дахь мөрөнд $n - 1$ үсгээс (үсэг бүр '$N$', '$E$', '$S$', эсвэл '$W$' байна) бүрдэх тэмдэгт мөр байх буюу эхний хүснэгтэн зам юм. Эдгээр үсгүүд нь хүснэгтэн зам дээгүүр аялах үйлдлүүдийн дараалал байна. Жишээлбэл бодлогын нөхцөл дахь замыг "$NNESWW$" тэмдэгт мөрөөр илэрхийлж болно.

Оролтын гурав дахь мөрөнд $n - 1$ үсгээс (үсэг бүр '$N$', '$E$', '$S$', эсвэл '$W$' байна) бүрдэх тэмдэгт мөр байх буюу хоёр дахь хүснэгтэн зам юм.

Гаралт

Хэрвээ хоёр бөмбөгийг нэгэн зэрэг төгсгөлийн байрлалд нь аваачих боломжтой бол "$YES$" (хашилтгүйгээр) гэж хэвлэ. Бусад тохиолдолд "$NO$" (хашилтгүйгээр) гэж хэвлэ. Аль ч тохиолдолд хариултыг томоор ч бичиж болно жижгээр ч бичиж болно.

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

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

Оролт
7
NNESWW
SWSWSW
Гаралт
YES
Оролт
3
NN
SS
Гаралт
NO

Тэмдэглэл

Эхний жишээн дээр эхний хүснэгтэн зам нь бодлогын нөхцөлд тодорхойлогдсон. Түүнчлэн дараах үйлдлүүдийн дараалал хоёр бөмбөгийг төгсгөлийн квадратад аваачна: $NNESWWSWSW$.

Хоёр дахь жишээн дээр ямар ч үйлдлүүдийн дараалал хоёр бөмбөгийг төгсгөлд аваачиж чадахгүй.

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