E. Эмх цэгц

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

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

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

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

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

Саймоны гэр дээрээсээ $n$ мөр $m$ баганатай тэгш өнцөгт хүснэгт шиг харагддаг. Хүснэгтийн бүх мөрүүд дээрээсээ доош $1$-ээс $n$ хүртэл дугаарлагдсан, баганууд нь зүүнээсээ баруун луу $1$-ээс $n$ хүртэл дугаарлагдсан болно. Хүснэгтийн нүд бүр нь өрөө юм. $x$ дүгээр мөр $y$ дүгээр баганы огтлолцод байрлах өрөөг ($x, y$) хосоор тэмдэглэнэ. Өрөө бүрийн хувьд гэрэл асаалттай эсвэл унтраастай байгааг бид мэднэ.

Одоогоор Саймон ($x_0, y_0$) өрөөнд байна. Тэр байшин дахь бүх өрөөний гэрлүүдийг унтраагаад ($x_0, y_0$) өрөөнд буцаж ирэхийг хүснэ. Саймонийг яг одоо ($x, y$) өрөөнд байна гэж үзье. Хүссэн үр дүндээ хүрэхийн тулд тэр дараах алхмуудыг хийж чадна.

  1. “1” хэлбэрийн үйлдлийг хийж ($x ,y$) өрөөний гэрлийг асаана. Саймон өрөөний гэрэл асаалттай байвал энэ үйлдлийг хийж чадахгүй.
  2. “2” хэлбэрийн үйлдлийг хийж ($x, y$) өрөөний гэрлийг унтраана. Саймон өрөөний гэрэл унтраастай байвал энэ үйлдлийг хийж чадахгүй.
  3. “$dir$” хэлбэрийн үйлдлийг хийж $dir$ чиглэлийн зэргэлдээ байрлалтай өрөө лүү орно. Чиглэл зүүн, баруун, дээш эсвэл доош байна (харгалзах $dir$ $L$, $R$, $U$, эсвэл $D$ байна). Нэмж хэлэхэд, Саймон $dir$ чиглэлд гэрэл харагдаж байгаа нөхцөлд л хөдлөнө. Хэрэв бид Саймоны явахыг хүсч байгаа өрөөг ($nx, ny$) гэж тэмдэглэвэл бидэнд байшингийн гэрэлтэй өрөөний тоо ($x + (nx - x)k, y + (ny - y)k$) байх $k$ ($k > 0$) бүхэл тоо байх ёстой. Мэдээж Саймон байшингаас гарч болохгүй.

Саймонд хүссэн үр дүндээ хүрэхэд хийх үйлдлүүдийн дарааллыг олоход туслаарай.

Оролт

Эхний мөрөнд $n$, $x_0$, $y_0$ ($2 ≤ n ≤ 500$, $1 ≤ x_0, y_0 ≤ n$) 3 ширхэг бүхэл тоо байна.

Дараагийн $n$ мөрүүд байшингийн өрөөнүүдийн тодорхойлолтуудыг агуулна. $i$ дүгээр мөр $n$ ширхэг хоосон зайгаар тусгаарлагдсан $a_{i1}, a_{i2}, ... , a_{in}$ бүхэл тоонуудыг агуулна. Хэрэв $a_{ij}$ тоо $0$ байвал ($i, j$) өрөөний гэрэл унтраастай байна гэсэн үг ба $а_{ij}$ нь $1$-тэй тэнцүү байвал гэрэл асаалттай байна гэсэн үг. Дор хаяж нэг өрөөний гэрэл асаалттай байгаа нь баталгаатай болно.

Гаралт

Хэрэв бүх гэрлийг унтраах боломжит дараалал байхгүй байвал “NO” гэж хэвлэнэ (хашилтгүй). Өөр тохиолдолд “YES” гэж хэвлэх (хашилтгүй) ба нөхцлийг хангасан үйлдлүүдийн дарааллыг тэмдэгт мөрөөр хэвлэнэ. Та хамгийн богино үйлдлийн дарааллыг олох шаардлагагүй, тэгэхдээ $3·10^6$-с олон үйлдлэл хийлгэх хэрэггүй.

Орчуулсан: Энхдүүрэн

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

Оролт
3 1 1
1 0 0
0 1 0
1 0 0
Гаралт
YES
D1R2L2D2UU2
Оролт
3 1 1
1 0 0
0 1 0
0 0 1
Гаралт
NO
Сэтгэгдлүүдийг ачааллаж байна...