C. Мөсөн агуй

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

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

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

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

Таны тоглож байгаа компьютерийн тоглоомын тоглоомын баатар олон давхар мөсөн агуйн аль нэг давхарт зогсож байна. Цааш явахын тулд ахин нэг давхар доошоо буух хэрэгтэй ба үүнийг хийх ганц арга нь мөсийг цөмлөн доош унах юм.

Одоо байгаа агуйн давхар нь $m$ багана болон $n$ мөрүүдээс бүрдсэн тор юм. Энэ торны нүд бүр нь бүтэн эсвэл хагарсан мөснөөс тогтоно. Та аль нэг нүднээс түүний зэргэлдээх нүд рүү үсэрч чадна (энд тоглоомын хязгаарлалтын дагуу та өөрийн зогсож байгаа нүдэндээ үсэрч чадахгүй, өөрөөр хэлбэл дороо үсэрч чадахгүй). Хэрвээ та хагарсан мөстэй нүд рүү үсэрвэл тоглоомын баатар доошоо унана, харин бүтэн мөстэй нүд рүү үсэрвэл тухайн мөс хагарах боловч та доошоо унахгүй дээр нь байна.

Мөрүүдийг дээрээс доош $1$-ээс $n$ хүртэлх бүхэл тоогоор, харин багануудыг зүүнээс баруун тийш $1$-ээс $m$ хүртэлх бүхэл тоогоор дугаарлая. $r$-р мөр болон $c$-р баганын огтлолцлын нүдийг $(r, c)$ гэж тэмдэглэнэ.

Та одоо $(r_{1}, c_{1})$ нүдэнд зогсож байгаа бөгөөд дээд давхраас энэ давхарт унасан учраас энэ нүд хагархай мөстэй байна. Та дараагийн давхарт орохын тулд $(r_{2}, c_{2})$ нүдээр доош унах хэрэгтэй. Та үүнийг хийж чадах уу?

Оролт

Эхний мөрөнд агуйн тодорхойлолтод байсан мөр болон баганын тоо болох $n$, $m$ ($1 ≤ n, m ≤ 500$) бүхэл тоонууд байна.

Дараагийн $n$ мөрүүдэд агуйн давхрын анхны байдлыг тодорхойлсон байх ба мөр бүр нь $m$ ширхэг "." (бүтэн мөс) эсвэл "X" (хагархай мөс) тэмдэгт агуулсан байна.

Дараагийн мөрөнд таны анхны байрлалын координатууд болох $r_{1}$, $c_{1}$ ($1 ≤ r_{1} ≤ n, 1 ≤ c_{1} ≤ m$) бүхэл тоонууд байна. Дээр тодорхойлсончлон $(r_{1}, c_{1})$ нүдэнд хагархай мөс буюу "X" тэмдэгт байна.

Дараагийн мөрөнд доош унах ёстой нүдний координатууд болох $r_{2}$, $c_{2}$ ($1 ≤ r_{2} ≤ n, 1 ≤ c_{2} ≤ m$) бүхэл тоонууд байна. Төгсгөлийн нүдний байрлал эхэлсэн нүдний байрлалтай давхцаж болно.

Гаралт

Хэрэв зорилгодоо хүрэх боломжтой бол "YES" гэж хэвлэнэ, эсрэг тохиолдолд "NO" гэж хэвлэнэ.

Орчуулсан: Даариймаа

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

Оролт
4 6
X...XX
...XX.
.X..X.
......
1 6
2 2
Гаралт
YES
Оролт
5 4
.X..
...X
X.X.
....
.XX.
5 3
1 1
Гаралт
NO
Оролт
4 7
..X.XX.
.XX..X.
X...X..
X......
2 2
1 6
Гаралт
YES

Тэмдэглэл

Эхний жишээнд ганц л боломжит зам байна. Энэ нь:

$(1, 6)$ → $(2, 6)$ → $(3, 6)$ → $(4, 6)$ → $(4, 5)$ → $(4, 4)$ → $(4, 3)$ → $(4, 2)$ → $(4, 1)$ → $(3, 1)$ → $(2, 1)$ → $(2, 2)$ → $(2, 3)$ → $(1, 3)$ → $(1, 2)$ → $(2, 2)$

Эхний удаа $(2, 2)$ нүдэнд очиход мөс хагарна, хоёр дахь удаагаа очиход таны тоглоомын баатар доош унаж зорилгодоо хүрнэ.

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