#include<bits/stdc++.h>
using namespace std;

int n,m,a[1001][1001],dr[1001][1001],v[1001][1001];
int si,sj,ei,ej;

queue<pair<int,int>> q;
priority_queue<pair<int,pair<int,int>>> walk;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
    {
        char x;
        cin>>x;
        if(x=='I')
        {
            si=i;
            sj=j;
        }
        if(x=='O')
        {
            ei=i;
            ej=j;
        }
        if(x=='*')
            a[i][j]=1;
        if(x=='D'){
            q.push({i,j});
            dr[i][j]=1;
        }
    }

    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        if(x<n&&!dr[x+1][y]&&a[x+1][y]!=1){
            dr[x+1][y]=dr[x][y]+1;
            q.push({x+1,y});
        }
        if(x>1&&!dr[x-1][y]&&a[x-1][y]!=1){
            dr[x-1][y]=dr[x][y]+1;
            q.push({x-1,y});
        }
        if(y<m&&!dr[x][y+1]&&a[x][y+1]!=1){
            dr[x][y+1]=dr[x][y]+1;
            q.push({x,y+1});
        }
        if(y>1&&!dr[x][y-1]&&a[x][y-1]!=1){
            dr[x][y-1]=dr[x][y]+1;
            q.push({x,y-1});
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
        cout<<dr[i][j]<<" ";
        cout<<endl;
    }

    walk.push({dr[si][sj],{si,sj}});

    while(!walk.empty())
    {
        int x = walk.front().second.first;
        int y = walk.front().second.second;
        walk.pop();

        if(x<n&&!v[x+1][y]&&a[x+1][y]!=1){
            v[x+1][y]=v[x][y]+1;
            walk.push({x+1,y});
        }
        if(x>1&&!v[x-1][y]&&a[x-1][y]!=1){
            v[x-1][y]=v[x][y]+1;
            walk.push({x-1,y});
        }
        if(y<m&&!v[x][y+1]&&a[x][y+1]!=1){
            v[x][y+1]=dr[x][y]+1;
            walk.push({x,y+1});
        }
        if(y>1&&!dr[x][y-1]&&a[x][y-1]!=1){
            dr[x][y-1]=dr[x][y]+1;
            q.push({x,y-1});
        }
    }
}