D. Артур ба хананууд

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

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

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

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

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

Артурын олсон байрны бүдүүвч зураг нь $1 × 1$ хэмжээтэй квадратуудаас бүрдсэн $n × m$ хэмжээтэй тэгш өнцөгт шиг харагддаг. Эдгээр квадрат бүр хана эсвэл хоосон зай байна. Бүдүүвч зураг дээр хэрвээ хана бол "$*$" тэмдгээр, хоосон зай бол "$.$" тэмдгээр дүрсэлнэ.

Хоосон зайнаас бүрдсэн хамгийн их үргэлжилсэн талбай бол байрны өрөө юм. Хэрвээ квадратууд хажуу талаараа холбогдсон бол зэргэлдээ квадратууд гэж үзнэ.

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

Оролт

Оролтын эхний мөрөнд $n, m$ ($1 ≤ n, m ≤ 2000$) хоёр бүхэл тоо байна. Эдгээр нь Артурын байрны хэмжээг илэрхийлнэ.

Дараагийн $n$ мөрүүдэд байрны бүдүүвч зураг байх бөгөөд мөр бүр $m$ ширхэг тэмдэгтүүд агуулна.

Хэрвээ тухайн нүд хана агуулж байгаа бол "$*$" тэмдгээр илэрхийлнэ.

Харин хоосон зайг эсвэл өрөөний хэсгийг агуулсан бол "$.$" тэмдгээр илэрхийлнэ.

Гаралт

Мөр бүр нь $m$ ширхэг тэмдэгтүүд агуулсан $n$ мөрүүд хэвлэнэ. Эдгээр мөрүүд өрөө бүрийг тэгш өнцөгт хэлбэртэй болгохын тулд боломжит хамгийн цөөхөн ханыг арилгасны дараа харагдах хэлбэр юм.

Хэд хэдэн хариулт байгаа бол тэдгээрийн аль нэгийг хэвлэнэ.

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

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

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