D. Одны дүрслэл

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

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

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

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

Берланд дахь одон орны зураг нь $n × m$ нүдтэй талбар байна. Нүд бүрт од байна эсвэл байхгүй. Берландын бүх одон орончдын дуртай одны дүрслэл бол загалмай дүрслэл юм. Энэ дүрслэл нь дурын таван одоор дүрслэгдэж болох ба бүхэл тоон утга $x$-н (дүрслэлийн радиус) хувьд дараах зүйлүүд үнэн:

  • 2-р од 1-р одтой нэг босоо шулуунд оршино гэвч $x$ дээшээ тооцогдоно
  • 3-р од 1-р одтой нэг босоо шулуунд оршино гэвч $x$ доошоо тооцогдоно
  • 4-р од 1-р одтой нэг хэвтээ шулуунд оршино гэвч $x$ зүүн тийш тооцогдоно
  • 5-р од 1-р одтой нэг хэвтээ шулуунд оршино гэвч $x$ баруун тийш тооцогдоно

Ийм дүрслэл нь маш олон байж болох учир эдгээрийг 1-с эхлүүлээд бүхэл тоогоор дараах зарчмийн дагуу дугаарлана: хоёр дүрслэл харьцуулагдах үед бага радиустай нь бага индекс авна; хэрвээ тэдний радиус ижил байвал аль өндөр төв одтой нь бага индекс авна; хэрвээ тэдний төв од нь ижил түвшинд байвал төв од нь зүүн талд нь байгаа нь бага индекс авна.

Таны ажил бол өгөгдсөн Берландын одон орны зургийн $k$ индекстэй дүрслэлийг олох юм.

Оролт

Эхний мөрөнд гурван бүхэл тоон утга $n$, $m$ ба $k$ ($1 ≤ n, m ≤ 300, 1 ≤ k ≤ 3*10^{7}$) байх ба харгалзан зургийн өндөр болон өргөн ба шаардлагатай дүрслэлийн индекс байна. Зүүн дээд булан $(1, 1)$ байх ба баруун доод булан $(n, m)$ байна. Тэгээд тус бүрдээ $m$ тэмдэгттэй $n$ мөр байх ба энэ нь зургийн тодорхойлолт юм. Хэрвээ $i$-р мөрний $j$-р тэмдэгт нь хэрвээ харгалзах нүд нь одтой бол «*» байна харин одгүй бол «.» байна.

Гаралт

Хэрвээ дүрслэлүүдийн тоо $k$-с бага бол $-1$-г хэвлэ. Бусад тохиолдолд тус бүрдээ хоёр бүхэл тоотой 5 мөр хэвлэнэ. Шаардлагатай дүрслэлийн координатууд юм. Оддыг дараах дарааллаар хэвлэ: төв, дээд, доод, зүүн, баруун.

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

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

Оролт
5 6 1
....*.
...***
....*.
..*...
.***..
Гаралт
2 5
1 5
3 5
2 4
2 6
Оролт
5 6 2
....*.
...***
....*.
..*...
.***..
Гаралт
-1
Оролт
7 7 2
...*...
.......
...*...
*.***.*
...*...
.......
...*...
Гаралт
4 4
1 4
7 4
4 1
4 7
Сэтгэгдлүүдийг ачааллаж байна...