// O(n^4 * m * 10)

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

#define N (42)
#define M (405)

const int inf = 10000010;
int n, m;
int f[M][N][N],s[M][M],g[M];
int ttt[N];
int gc[M][N][N][N];
int ans[N][M];
char a[N][M];
char ga[M][N][N][N][10],gb[M][N][N][N][10];
//int ga[M][N][N][N],gb[M][N][N][N];

int cal(int i, int j, int k){
	g[j-1] = 0;
	for (int x = j; x <= k; x++){
		g[x] = inf;
		ttt[x] = 0;
	}
	for (int z = 0; z <= 9; ++z){
		for (int x = k; x >= j; --x){
			for (int w = j - 1, tmp; w < x; ++w){
				tmp = g[w] + s[x][z] - s[w][z] + f[i+1][w+1][x];
				if (g[x] > tmp){
					g[x] = tmp;
//					printf("%d %d %d %d %d %d\n", i+1, j, k, x,w,z);
					ttt[x] = z;
					ga[i+1][j][k][x][z]=w;
					gb[i+1][j][k][x][z]=ttt[w];
					
				}
			}
		}
	}
	gc[i+1][j][k][k] = ttt[k];
	return g[k];
}
int get2(int i, int j, int k){
	g[j-1] = 0;
	for (int x = j; x <= k; x++){
		g[x] = inf;
		ttt[x] = 0;
	}
	for (int z = 0; z <= 9; ++z){
		for (int x = k; x >= j; --x){
			for (int w = j - 1, tmp; w < x; ++w){
				tmp = g[w] + s[x][z] - s[w][z] + f[i+1][w+1][x];
				if (g[x] > tmp){
					g[x] = tmp;
//					printf("%d %d %d %d %d %d\n", i+1, j, k, x,w,z);
					//ttt[x] = z;
					//ga[i+1][j][k][x]=w;
					//gb[i+1][j][k][x]=z;
				}
			}
		}
	}
//	gc[i+1][j][k][k] = ttt[k];
	return g[k];
}
void get(int i, int j, int k){
	if (i==m) return;
	int p = k, q = gc[i+1][j][k][k];
	while (1){
		//printf("%d %d %d\n", i, p, q);
		int pp = ga[i+1][j][k][p][q], qq = gb[i+1][j][k][p][q];
		for (int t = pp+1; t<=p;t++){	
			ans[t][i+1] = q;
		}
		get(i+1,pp+1,p);
		p = pp;
		q = qq;
		if (p < j) break;
	}
	/*int q = k, p = ga[i+1][j][k][k];
	while (1){
		for (int t = p + 1; t <= q; t++){
			ans[t][i+1] = gb[i+1][j][k][q];
		}
		get(i+1,p+1,q);
		q = p;
		p = ga[i+1][j][k][p];
		if (q < j) break;*/
}
int main(){
	scanf("%d%d", &n, &m);
	for (int i = 1;i <=n;i++){
		scanf("%s", a[i] + 1);
		for (int j = 1; j <= m; j++){
			a[i][j] -= '0';
		}
	}
	for (int i = m; i >= 0; i--){
		for (int p = 0; p <= 9; p++){
			for (int k = 1; k <= n; k++){
				s[k][p] = s[k - 1][p] + (a[k][i+1] != p);
			}
		}
		for (int j = 1; j <= n; j++){
			for (int k = j; k<= n; k++){
				f[i][j][k] = cal(i, j , k);
			}
		}
	}
	get(0,1,n);
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			printf("%d", ans[i][j]);
		}
		printf("\n");
	}
	//printf("%d\n", f[0][1][n]);
}