D. Хархнууд

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

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

оролт input.txt

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

Василый Петровичийн дэлгүүрийн зооринд хархнууд зуу зуугаараа үүрлэжээ. Василый Петрович тэдний байгааг хараагүй боловч дэлгүүрийн зоориноос хүнс алдагдсаар байв. Василый Петрович энэ явдлыг тэвчиж чадахгүй тул хархнуудыг устгахаар шийджээ. Хархны хавх хуучирсан арга болж, хархны хор хүмүүсийг хордуулж магадгүй тул тэрээр яг $2$ гранатаар тэднийг устгахаар шийджээ.

Энэ бодлогонд бид зоорийг $n × m$ нүдтэй тэгш өнцөгт хүснэгт гэж үзнэ. Зарим нүднүүдэд хана байх ба үлдсэн нь хоосон байна. Василый Петрович хархнуудыг судалсны эцэст тэднийг унтахдаа үргэлж нэг байрандаа унтдагийг мэдсэн тул тэр үед нь гранатаа дэлбэлэхийг хүсчээ. Тэрээр тэдний унтдаг газруудыг хүснэгтийн нүднүүдэд тэмдэглэжээ. Мэдээж тэр нүднүүд нь ханатай давхцахгүй байх болно.

Гранат зөвхөн ханагүй нүдийг цэвэрлэж чадна. Гранатын тэсрэлт дараах байдалтай байна. Гранатыг $0$ агшинд дэлбэлсэн гэж үзье. Энэ агшинд зөвхөн гранат байрласан нүд л цэвэрлэгднэ. Хэрэв $t$ агшинд ямар нэгэн нүд цэвэрлэгдсэн гэвэл $t+1$ агшинд түүний хөрш ханагүй нүд бүр цэвэрлэгдэнэ. Зарим хананууд аль хэдийн гранатанд цэвэрлэгдсэн байж болно. Гранатын тэсрэлт яг $d$ секунд үргэлжлэн дуусна.

Гранатын тэсрэлтийн жишээ: Эхний зураг тэсрэлтийн өмнөх байдлыг үзүүлсэн ба удаах зургууд нь $0$, $1$, $2$, $3$ ба $4$ дэхь секундэд цэвэрлэгдсэн нүднүүдийг үзүүлсэн байна. Гранатын тэсрэлт $d = 4$ секүндийн турш үргэлжилсэн.

Василыи Петрович бүх хархнуудыг устгаж чаддаг байхаар гранад суурилуулах $2$ нүд байгаа эсэхийг мэдэхийг хүсчээ. Түүнийг олж мэдэх програм зохионо уу.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан гурван бүхэл тоо $n$, $m$ ба $d$ байна $(4 ≤ n, m ≤ 1000, 1 ≤ d ≤ 8)$. Дараагийн $n$ мөрөнд зоорины зургийг дүрсэлсэн байх ба мөр бүрт $m$ ширхэг тэмдэгт байна. "X" тэмдэгтээр ханатай нүдийг, "." тэмдэгтээр хоосон нүдийг, "R" тэмдэгтээр харх унтаж байгаа нүдийг тэмдэглэсэн байна.

Өгөгдөлд эхний болон сүүлийн мөрүүд, эхний болон сүүлийн баганууд "X" тэмдэгтээс тогтно. Мөн хүснэгтэнд дор хаяж нэг харх байрласан байна.

Гаралт

Хэрэв бүх хархыг устгах боломжгүй бол "-1" гэж хэвлэнэ. Бусад тохиолдолд эхний гранат $(r_{1}, c_{1})$ нүдэнд нөгөө гранат нь $(r_{2}, c_{2})$ нүдэнд байрлах ёстойг илэрхийлэх зайгаар тусгаарлагдсан 4 бүхэл тоо $r_{1}, c_{1}, r_{2}, c_{2}$-г хэвлэнэ үү.

Хүснэгтийн мөрүүдийг дээрээс нь доош $1$-ээс $n$ хүртэл, багануудыг зүүнээс баруун тийш $1$-ээс $m$ хүртэл дугаарласан гэж үзье. $r_{1}$ ба $r_{2}$ нар нь мөрийн дугаар мөн $c_{1}$ ба $c_{2}$ нар нь баганын дугаарыг илэрхийлэх ба $1 ≤ r_{1}, r_{2} ≤ n, 1 ≤ c_{1}, c_{2} ≤ m$ нөхцлийг хангана. $2$ гранатыг ижил нүдэнд байрлуулж болохгүй ба тэсрэлтүүд огтлолцож болно. Нэг гранат нь нэг ч харх устгахгүй байхад нөгөөх нь бүгдийг нь устгаж болно.

Орчуулсан: Бат-Од

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

Оролт
4 4 1
XXXX
XR.X
X.RX
XXXX
Гаралт
2 2 2 3
Оролт
9 14 5
XXXXXXXXXXXXXX
X....R...R...X
X..R.........X
X....RXR..R..X
X..R...X.....X
XR.R...X.....X
X....XXR.....X
X....R..R.R..X
XXXXXXXXXXXXXX
Гаралт
2 3 6 9
Оролт
7 7 1
XXXXXXX
X.R.R.X
X.....X
X..X..X
X..R..X
X....RX
XXXXXXX
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...