#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

#include <iostream>

using namespace std;

const int maxn=1e5+;

typedef long long ll;

//dp[i][j] 表示前i个数，修改不超过j次的最小值。 dp[i][j]向dp[i+1][j+k]转移

//pre[i][j]表示第i个数修改j次是由第i-1个数修改pre[i][j]次转移过来的。

string dp[][],unite,str[];

int pre[][];

char a[][];

int n,m;

string judge(int x){

    string ans;

    ans.clear();

    for(int i=;i<m;i++){

        int num=a[][i]-'';

        if(num&&x) {

            x--;

            ans+='';

        }

        else ans+=num+'';

    }

    return ans;

}

bool Min(string u,string v){

    for(int i=;i<m;i++){

        if(u[i]!=v[i]){

            if(u[i]>v[i]) return false;

            return true;

        }

    }

    return true;

}

string judge(string ss,int x,int k){

    // printf("k=%d\n",k);

    string ans;ans.clear();

    int cnt=,mark=-,sum=k;

    for(int i=;i<m;i++){

        ans+=a[x][i];

        if(a[x][i]!=ss[i]) cnt++;

    }

    if(k==){

        if(Min(ss,ans)==) return unite;

        return ans;

    } 

    if(cnt<=k) return ss;

    for(int i=;i<m;i++){

        if(a[x][i]!=ss[i]){

            if(k) {

                k--;

                ans[i]=ss[i];

                if(k==) mark=i;

            }

        }

    }

    // printf("mark=%d\n",mark);

    if(Min(ss,ans)) return ans;

    for(int i=mark;i>=;i--){

        if(ans[i]!=''){

            ans[i]++;

            int flag=,num=;

            for(int j=i+;j<m;j++) ans[j]=a[x][j];

            for(int j=;j<m;j++){

                if(ans[j]!=a[x][j]) num++;

            }

            num=sum-num;

            for(int j=i+;j<m&&num;j++){

                if(ans[j]-''){

                    ans[j]='';

                    num--;

                }

            }

            return ans;

        }

    }

    return unite;

}

//43435

//

void init(){

    unite.clear();

    for(int i=;i<=m;i++) unite+='a';

}

int main(){

    scanf("%d%d",&n,&m);init();

    for(int i=;i<=n;i++){

        scanf("%s",a[i]);

    }

    int len=;

    for(int i=;i<=n;i++){

        for(int j=;j<=len;j++){

            dp[i][j]=unite;

        }

    }

//    printf("len=%d\n",len);

    for(int i=;i<=len;i++) dp[][i]=judge(i);

    for(int i=;i<n;i++){

        for(int j=;j<=len;j++){

            for(int k=;k+j<=len;k++){

                string tmp=judge(dp[i][j],i+,k);

                // printf("i=%d j=%d k=%d\n",i,j,k);

                // cout<<dp[i][j]<<endl;

                // cout<<tmp<<endl;

                if(Min(dp[i+][j+k],tmp)==){

                    // printf("i=%d j=%d k=%d\n",i,j,k);

                    // cout<<dp[i][j]<<endl;

                    // cout<<dp[i+1][j+k]<<endl;

                    // cout<<tmp<<endl;

                    dp[i+][j+k]=tmp;

                    pre[i+][j+k]=j;

                    // printf("pre[%d][%d]=%d\n",i+1,j+k,j);

                }

            }

        }

    }

    //printf("www\n");

    int mark=;

    for(int i=;i<=len;i++){

//        printf("i=%d ",i);

    //    cout<<dp[n][i]<<endl;

        if(Min(unite,dp[n][i])==){

            mark=i;

            break;

        }

    }

    // printf("%d\n",mark);

    for(int i=n;i>=;i--){

        str[i]=dp[i][mark];

        mark=pre[i][mark];

    }

    for(int i=;i<=n;i++) cout<<str[i]<<endl;

    return ;

}

/*

5 4

9999

0000

9999

0000

9999

*/