Zen

Note: Bài này ngang 3500 bên codeforces
Công viên Thiền nằm trên một lưới ô vuông, các ô vuông là cát hoặc là đá. Kiến trúc sư nhận thấy công viên này còn rất bừa bộn. Khu vườn Thiền đẹp phải có dạng hình chữ nhật, mọi ô bên trong hình chữ nhật đều là ô cát và nếu có các ô giáp biên với hình chữ nhật này thì các ô đó phải là ô đá.
Bây giờ bạn đã được yêu cầu, với tư cách là một chuyên gia xây dựng, cần loại bỏ càng ít các ô đá càng tốt để có được những khu vườn Thiền đẹp(khi một ô đá nào đó được loại bỏ thì ô đó sẽ trở thành ô cát). Trong ví dụ dưới, các ô vuông có dấu chấm (.) là cát và các ô vuông có dấu thăng (#) là đá. Sau khi loại bỏ 6 ô đá ở Hình A thì ta được 2 khu vườn Thiền đẹp như Hình B. Ở Hình C thì ta không cần xoá ô đá nào.

Yêu cầu: Cho một lưới ô vuông kích thước N x M, hãy loại bỏ ít ô đá nhất để làm cho khu vườn Thiền trở nên đẹp và in ra khu vườn Thiền sau khi sửa trông như thế nào.

Input:

• Dòng đầu tiên ghi số nguyên \(N\) và \(M\) lần lượt là số hàng và số cột của công viên Thiền \((1 \le N, M \le 10^3)\).
• Mỗi dòng trong \(N\) dòng tiếp theo sẽ là một chuỗi \(M\) ký tự '.' nếu ô vuông là cát và '#' nếu ô vuông tương ứng là đá.

Output:

• Ghi ra tệp văn bản ZEN.OUT gồm một ma trận kích thước \(N \times M\), mô tả khu vườn Thiền sẽ trông như thế nào sau khi loại bỏ số lượng đá nhỏ nhất.

Lưu ý: Giải pháp của bạn bị sai nếu vẫn còn khu vườn Thiền chứa các ô là cát mà không phải là khu vườn Thiền đẹp.

Example

6 6
###...
#.#...
..#...
..#.##
..##.#
###..#

###...
..#...
..#...
..#...
..#...
###...

3 3
###
###
###

###
###
###