D. Эвдэрхий дэлгэц

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

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

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

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

Инноцентусын дэлгэц гэмтсэн байна. Дэлгэцийн зарим пиксэл нь "үхчихсэн". Тэдгээр нь үргэлж хар байдаг болжээ. Инноцентус энэ асуудалтай байхдаа энгийн компьютер тоглоом тоглож чадахгүй байна. Тэгээд тэр Поликарпус дүүтэйгээ дараах тоглоомыг тоглож байна.

Инноцентус бүтэн хар дэлгэцийн тодорхой талтай квадратын хүрээг цагаанаар буддаг програм бичсэн. Энэ үед дэлгэцийн эвдэрхий пикселүүд хараараа л үлдэх билээ. Ингээд Поликарпус дэлгэцрүү хараад, Инноцентусын будсан квадратын байрлал ба хэмжээг олох ёстой. Поликарпус тоглох дургүй байхад ах нь уг тоглоом "анхаарал ба төсөөллийг хөгжүүлнэ" гэж хэлээд тоглохыг шаарджээ.

Поликарпуст тусалж, дараах шаардлагыг хангадаг квадратыг олдог програм зохиож өгөөрэй. Үүнд:

  • Хүрээний өргөн $1$ пиксел
  • Хүрээ дэлгэцийн хязгаараас хэтрэхгүй
  • Дэлгэцэнд бүх цагаан пиксел багтана
  • Дээрх нөхцлүүдийг хангах квадратуудаас хамгийн бага талбайтай нь байх ёстой.

Жишээ нь хүрээний урт $d = 3$ бол $8$ цагаан нүд байх юм. Хэрвээ $d = 2$ бол $4$ нүд будагдах ба $d = 1$ бол хүрээ маань ганц пиксел болно.

Оролт

Эхний мөрөнд дэлгэцийн нягтралыг илэрхийлэх $n$, $m$ ($1 ≤ n, m ≤ 2000$) тоонууд өгөгдөнө. Дараагийн $n$ мөр бүрт $m$ тэмдэгт өгөгдөх бөгөөд энэ нь тоглоомын дэлгэцийн мэдээлэл юм. "." (цэг, ASCII код нь $46$) нь хар пикселийг, "w" (Латин цагаан толгойн жижиг w) нь цагаан пикселийг илэрхийлнэ. Дэлгэцэнд ядаж ганц цагаан пиксел байгаа болно.

Гаралт

Сэргээгдсэн цэгүүдийг "+" (нэмэх тэмдэг)-р илэрхийлж дэлгэцийг хэвлэ. Оролтонд цагаан байсан цэгүүд өөрчлөгдөх ёсгүй. Тэдгээрийн "w"-р хэвлэ. Хэрвээ олон янзаар зөв хариуг үүсгэх боломжтой бол алийг нь ч хэвлэж болно.

Хэрвээ шаардлага хангах хүрээ байхгүй бол -1 -г хэвлэнэ.

Орчуулсан: zoloogg

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

Оролт
4 8
..w..w..
........
........
..w..w..
Гаралт
..w++w..
..+..+..
..+..+..
..w++w..
Оролт
5 6
......
.w....
......
..w...
......
Гаралт
......
+w+...
+.+...
++w...
......
Оролт
2 4
....
.w..
Гаралт
....
.w..
Оролт
2 6
w..w.w
...w..
Гаралт
-1

Тэмдэглэл

In the first sample the required size of the optimal frame equals 4. In the second sample the size of the optimal frame equals 3. In the third sample, the size of the optimal frame is 1. In the fourth sample, the required frame doesn't exist.

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