#include<bits/stdc++.h>
using namespace std;
const int MAXN=200005;
const int MAXK=205;
const int INF=0x3f3f3f3f;
const int dir[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};

vector<int> e[MAXN<<1|1];
void dfs0(int u,int lim,vector<int>& vec)
{
    if(u<lim)
    {
        vec.push_back(u);
        return;
    }
    for(auto& v : e[u])
        dfs0(v,lim,vec);
}

int vis[MAXN],fa[MAXN];
vector<vector<int>> cirs;
int dfs1(int u)
{
    vis[u]=1;
    for(auto v : e[u])
    {
        if(!vis[v])
        {
            fa[v]=u;
            if(dfs1(v))return 1;
        }
        else if(vis[v]==1)
        {
            vector<int> cir;
            cir.push_back(v);
            for(int c=u; c!=v; c=fa[c])
                cir.push_back(c);
            reverse(cir.begin(),cir.end());
            cirs.push_back(move(cir));
            return 1;
        }
    }
    vis[u]=2;
    return 0;
}

int dep[MAXN],add[MAXN],top[MAXN],son[MAXN];
void dfs2(int u)
{
    top[u]=1;
    for(auto v : e[u])
    {
        if(vis[v]>=0)continue;
        fa[v]=u,vis[v]=vis[u],dep[v]=dep[u]+1;
        if(dep[u])add[v]=add[u];
        dfs2(v);
        top[u]+=top[v];
        if(son[u]<0 || top[v]>top[son[u]])son[u]=v;
    }
}

void dfs3(int u,int t)
{
    top[u]=t;
    if(son[u]>=0)dfs3(son[u],t);
    for(auto v : e[u])
        if(v!=u && vis[v]==vis[u] && v!=son[u])dfs3(v,v);
}
pair<int,int> lcad(int u,int v)
{
    int du=u,dv=v;
    while(u!=v)
    {
        if(dep[u]>dep[v])du=u,u=fa[u];
        else dv=v,v=fa[v];
    }
    return make_pair(du,dv);
}

int las[MAXN];
vector<int> buc[MAXN];
int dfs4(int u,int clen,vector<pair<int,int>>& can)
{
    if(las[dep[u]]>=0)
        can.emplace_back(u,las[dep[u]]);
    las[dep[u]]=u;
    buc[(vis[u]+dep[u])%clen].push_back(u);
    int res=dep[u];
    for(auto v : e[u])
    {
        if(v==u || vis[v]!=vis[u])continue;
        res=max(res,dfs4(v,clen,can));
    }
    return res;
}

string grid[MAXN];
char opstr[MAXK];
int op[MAXK],res[MAXN];

struct DSU
{
    int fa[MAXN];
    void init(int n)
    {
        iota(fa,fa+n,0);
    }
    int find(int x)
    {
        return fa[x]==x ? x : fa[x]=find(fa[x]);
    }
    bool merge(int x,int y)
    {
        x=find(x),y=find(y);
        if(x==y)return 0;
        return fa[x]=y,1;
    }
} dsu;

int main()
{
    int n,m,k;
    scanf("%d%d%d%s",&n,&m,&k,opstr);
    for(int i=0; i<k; i++)
    {
        if(opstr[i]=='U')op[i]=0;
        if(opstr[i]=='D')op[i]=1;
        if(opstr[i]=='L')op[i]=2;
        if(opstr[i]=='R')op[i]=3;
    }
    for(int i=0; i<n; i++)
    {
        static char buff[MAXN];
        scanf("%s",buff);
        grid[i]=buff;
    }
    auto go=[&](int i,int j,int d)
    {
        int ti=i+dir[d][0],tj=j+dir[d][1];
        if(ti<0 || ti>=n || tj<0 || tj>=m || grid[ti][tj]!='1')ti=i,tj=j;
        return make_pair(ti,tj);
    };
    int cur=0;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
        {
            if(grid[i][j]!='1')continue;
            ++cur;
            int ti=i,tj=j;
            for(int t=0; t<k; t++)
                tie(ti,tj)=go(ti,tj,op[t]);
            e[ti*m+tj].push_back(i*m+j);
        }
    fill(vis,vis+n*m,-1);
    for(int i=0, ts=0; i<n; i++)
        for(int j=0; j<m; j++)
        {
            if(grid[i][j]!='1')continue;
            vector<pair<int,int>> cur, tmp;
            for(auto v : e[i*m+j])
                cur.emplace_back(v,v);
            int rt=n*m;
            for(int t=0; t<k; t++,ts++)
            {
                int lim=rt;
                for(auto& [u,ur] : cur)
                {
                    auto [ux,uy]=go(u/m,u%m,op[t]);
                    if(vis[ux*m+uy]<ts)
                    {
                        vis[ux*m+uy]=ts;
                        las[ux*m+uy]=tmp.size();
                        tmp.emplace_back(ux*m+uy,ur);
                    }
                    else
                    {
                        if(tmp[las[ux*m+uy]].second<lim)
                        {
                            e[rt].push_back(tmp[las[ux*m+uy]].second);
                            tmp[las[ux*m+uy]].second=rt++;
                        }
                        e[tmp[las[ux*m+uy]].second].push_back(ur);
                    }
                }
                cur.swap(tmp);
                tmp.clear();
            }
            if(rt>n*m)
            {
                e[i*m+j].clear();
                dfs0(rt-1,n*m,e[i*m+j]);
                for(int t=n*m; t<rt; t++)
                    e[t].clear();
            }
        }
    fill(vis,vis+n*m,0);
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            if(grid[i][j]=='1' && !vis[i*m+j])
                dfs1(i*m+j);
    fill(vis,vis+n*m,-1);
    fill(son,son+n*m,-1);
    fill(las,las+n*m,-1);
    vector<tuple<int,int,int>> edges;
    for(size_t c=0; c<cirs.size(); c++)
    {
        int clen=cirs[c].size();
        for(int i=0; i<clen; i++)
        {
            vis[cirs[c][i]]=i;
            int du=cirs[c][(i+1)%clen];
            for(auto& dv : e[cirs[c][i]])
            {
                if(dv==du)continue;
                int xu=du/m,yu=du%m,xv=dv/m,yv=dv%m;
                for(int t=0; t<k && (xu!=xv || yu!=yv); t++)
                {
                    ++add[dv];
                    tie(xu,yu)=go(xu,yu,op[t]);
                    tie(xv,yv)=go(xv,yv,op[t]);
                }
            }
        }
        for(int i=0; i<clen; i++)
        {
            dfs2(cirs[c][i]);
            dfs3(cirs[c][i],cirs[c][i]);
            vector<pair<int,int>> can;
            int d=dfs4(cirs[c][i],clen,can);
            fill(las,las+d+1,-1);
            for(auto& [u,v] : can)
            {
                auto [du,dv]=lcad(u,v);
                int step=(dep[u]-dep[du])*k;
                int xu=du/m,yu=du%m,xv=dv/m,yv=dv%m;
                for(int t=0; t<k && (xu!=xv || yu!=yv); t++)
                {
                    ++step;
                    tie(xu,yu)=go(xu,yu,op[t]);
                    tie(xv,yv)=go(xv,yv,op[t]);
                }
                edges.emplace_back(step,u,v);
            }
        }
        for(int i=0; i<clen; i++)
        {
            sort(buc[i].begin(),buc[i].end(),[&](int x,int y)
            {
                return (dep[x]-1)*k+add[x]<(dep[y]-1)*k+add[y];
            });
            for(size_t j=0; j+1<buc[i].size(); j++)
                edges.emplace_back((dep[buc[i][j+1]]-1)*k+add[buc[i][j+1]],buc[i][j],buc[i][j+1]);
            buc[i].clear();
        }
    }
    fill(res,res+n*m+1,INF);
    res[cur]=0;
    sort(edges.begin(),edges.end());
    dsu.init(n*m);
    for(auto& [t,u,v] : edges)
    {
        cur-=dsu.merge(u,v);
        res[cur]=min(res[cur],t);
    }
    for(int i=1; i<=n*m; i++)
    {
        res[i]=min(res[i],res[i-1]);
        printf("%d\n",res[i]<INF ? res[i] : -1);
    }
    return 0;
}