Cháy rừng Berland

Khu rừng Berland được biểu diễn bởi một mặt phẳng vô hạn các ô vuông, ở mỗi ô có một cây.

Một đám cháy đã quét qua khu rừng. Bạn được cung cấp bản đồ kích thước $n\times m$ mô tả phần rừng bị ảnh hưởng. Ô cháy được đánh dấu là X, ô không cháy là .. Đảm bảo rằng mọi cây bị cháy trên toàn bộ rừng đều nằm trong bản đồ, và tất cả các cây bên ngoài bản đồ đều không bị thiệt hại.

Giả sử đám cháy bắt đầu vào thời điểm $0$ tại một tập hợp ô nào đó. Tại cuối mỗi phút, lửa lan từ mỗi ô đang cháy sang $8$ ô lân cận (kể cả đường chéo). Đến đầu phút thứ $T$, lửa được dập tắt. Bạn cần tìm giá trị $T$ lớn nhất có thể sao cho tồn tại một tập ô được đốt ban đầu mà sau $T$ phút lan tỏa cho ra đúng bản đồ ô cháy đã cho (và không có cây nào bên ngoài bản đồ bị cháy).

Với giá trị $T$ tối đa đó, hãy in ra một tập ô khởi điểm hợp lệ bất kỳ.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• $n$ dòng tiếp theo, mỗi dòng gồm $m$ ký tự X hoặc ., mô tả bản đồ.

Dữ liệu ra

• Dòng đầu in ra số nguyên $T$ — thời gian cháy lớn nhất có thể.
• $n$ dòng tiếp theo in ra bản đồ $n\times m$, trong đó các ô khởi điểm được đánh dấu là X, các ô còn lại là ..

Nếu có nhiều tập khởi điểm hợp lệ với $T$ lớn nhất, in ra một tập bất kỳ.

Ràng buộc

• $1\le n,m\le {10}^6$
• $1\le n·m\le {10}^6$
• Bản đồ chứa ít nhất một ô X.

Ví dụ