드로이드를 위한 낱말 퍼즐

R2-D2는 드로이드를 위해 만든 낱말 퍼즐을 풀고 있습니다. 이 퍼즐에서는 칸에 글자가 아니라 숫자를 씁니다.

퍼즐은 $n \times m$ 크기의 격자판입니다. 일부 칸은 막혀 있고, 나머지 칸은 빈칸입니다. 단어란 빈칸으로 이루어진 세로 또는 가로 구간 중 포함 관계로 극대인 것을 말합니다. 즉, 단어는 한 열이나 한 행에서 양쪽이 판의 가장자리 또는 막힌 칸으로 막힌 빈칸 구간입니다.

처음에 각 빈칸에는 숫자가 하나씩 적혀 있습니다. 드로이드의 목표는 모든 단어가 회문이 되도록 숫자를 바꾸는 것입니다. 회문은 왼쪽에서 읽든 오른쪽에서 읽든 같은 문자열입니다. 바꾼 숫자의 총 변화량은 적을수록 좋습니다. 따라서 모든 빈칸에 대해 원래 숫자와 해답 숫자 차이의 절댓값을 더한 합이 최소가 되는 해답을 구하세요.

R2-D2가 숫자 변화의 합을 최소로 하여 퍼즐을 풀도록 도와주세요. 모든 단어가 회문이 되도록 칸을 채우는 방법은 항상 있다는 것을 쉽게 알 수 있습니다. 예를 들어 모든 빈칸에 같은 숫자를 쓰면 됩니다. 따라서 해답은 항상 존재합니다.

첫 줄에 두 정수 $n$과 $m$이 주어집니다($1 \le n, m \le 1\,000$). 격자판의 크기입니다.

다음 $n$개 줄에는 각각 $m$개의 문자로 퍼즐이 주어집니다. 문자는 . 또는 숫자입니다. .은 막힌 칸이고, 숫자 $d$는 처음에 $d$가 적혀 있는 빈칸입니다.

입력과 같은 형식으로 해답 퍼즐을 출력하세요. 해답이 여러 개이면 아무거나 출력해도 됩니다.

첫 번째 예제에서는 퍼즐에 열과 행마다 하나씩, 총 6개의 단어가 있습니다. 최적 해답에서 숫자 변화의 합은 20입니다.

두 번째 예제에서는 길이 1인 단어 말고도 2020, 05, 10이라는 단어가 있습니다. 최적 해답에서 숫자 변화의 합은 7입니다.