Thầy Phú đang giải trò chơi ô chữ. Trong trò chơi ô chữ này, thầy cần viết vào các ô không phải là chữ cái mà là chữ số. Ô chữ là một lưới ô vuông n x 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 thầy phú 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, điều kiện quan trọng là thầy Phú 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 thầy Phú 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 đó! Nhưng bạn phải tìm ra cách làm tối ưu nhất!

Định dạng dữ liệu đầu vào

            Dòng đầu tiên chứa 2 số nguyên n và m - chiều rộng và chiều dài của lưới

            N dòng tiếp theo, mỗi dòng chứa m ký tự. Ký tự có thể là “.” hoặc cá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.

Định dạng dữ liệu đầu ra

            In ra bảng lưới ô vuông tối ưu sau khi thay đổi.

Ví dụ: