Tuấn đang giải trò chơi ô chữ. Trong trò chơi ô chữ này, Tuấn cần viết vào các ô không phải là chữ cái mà là chữ số. Ô chữ là một bảng có ~n×m~ ô. Một số ô bị chặn và các ô còn lại là trống. Một từ trong trò chơi ô chữ là đoạn con tối đa theo xét theo chiều dọc hoặc chiều ngang của các ô trống. Nói cách khác, một từ là một đoạn các ô của một cột hoặc một hàng, được giới hạn ở cả hai phía bởi cạnh của lưới hoặc các ô bị chặn. Ban đầu, mỗi ô trống chứa một chữ số.

Mục tiêu của Tuấn là thay đổi các chữ số để mỗi từ trong ô chữ là một palindrome (từ đối xứng). Palindrome là một chuỗi đọc từ trái qua phải hay từ phải qua trái thì đều giống nhau. Đồng thời, Tuấn phải tìm cách để tổng sự thay đổi của các chữ số trong bảng mới so với bảng ban đầu là nhỏ nhất có thể. Do đó, cần phải tìm lời giải sao cho giá trị tuyệt đối của hiệu giữa tổng các chữ số trong bảng ban đầu và tổng các chữ số của bảng mới là nhỏ nhất.

Hãy giúp Tuấn giải trò chơi sao cho tổng giá trị chữ số thay đổi là nhỏ nhất.

Có thể dễ dàng nhận thấy rằng luôn có một cách để giải ô chữ để tất cả các từ đều là palindromes. Ví dụ, điền vào tất cả các ô trống có cùng 1 số. Do đó, luôn tồn tại một cách làm nào đó, bạn phải tìm ra cách làm tối ưu nhất!

**Dữ liệu vào: **

• Dòng đầu tiên chứa 2 số nguyên dương ~n~ và ~m~ là chiều rộng và chiều dài của bảng ô chữ.
• ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ ký tự. Ký tự có thể là “.” hoặc chữ số. Nếu ký tự “.” là ô bị chặn. Nếu ký tự là chữ số ~d~ tương ứng với ô trống trong đó số ~d~ được viết từ ban đầu.

Kết quả: Ghi ra bảng lưới ô vuông tối ưu sau khi thay đổi.

Ví dụ:

Input

4 3
.2.
.05
.2.
10. 

Output

.1.
.22
.2.
11. 

**Ràng buộc: **

• Có 7% số test tương ứng với ~n,m ≤ 4~
• Có 6% số test khác tương ứng ~n = 1~
• Có 34% số test khác tương ứng với ~n,m≤100~
• Có 27% số test khác còn lại có ~n,m ≤ 300~
• Có 26% số test còn lại có ~n,m≤1000~