#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define int long long
#define V vector

const int inf = 1e9;
const int mxn = 4e5+50;

void chmin(int &a, int b) {
	a = min(a,b);
}

int n,m,k;
V<V<int>> g;
string s;
V<V<int>> gg[2];
V<array<int,2>> mg;

int kil[mxn],to[mxn];
int in_deg[mxn];
int depth[mxn];

vector<int> adj[mxn];
vector<array<int,3>> iter_order;

queue<int> topsort;

int cnt = 0, ans[mxn];

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	cin>>n>>m>>k>>s;
	g.resize(n+5);
	
	g[0].resize(m+5);
	g[n+1].resize(m+5);
	
	for (int i=1; i<=n; i++) {
		g[i].resize(m+5);
		for (int j=1; j<=m; j++) {
			char c; cin>>c;
			g[i][j] = c-'0';
			if (g[i][j]) cnt++;
		}
	}
	
	//macro
	for (int x=1; x<=n; x++)
		for (int y=1; y<=m; y++) {
			if (!g[x][y]) continue;
			int cx = x, cy = y;
			for (int i=0; i<k; i++) {
				if (s[i]=='U') {if (g[cx-1][cy]) cx--;}
				else if (s[i]=='D') {if (g[cx+1][cy]) cx++;}
				else if (s[i]=='L') {if (g[cx][cy-1]) cy--;}
				else if (s[i]=='R') {if (g[cx][cy+1]) cy++;}
			}
			to[x*m+y] = cx*m+cy;
			in_deg[cx*m+cy]++;
			adj[cx*m+cy].push_back(x*m+y);
		}
	for (int x=1; x<=n; x++)
		for (int y=1; y<=m; y++)
			if (g[x][y] && !in_deg[x*m+y])
				topsort.push(x*m+y);
	fill(depth,depth+mxn,1);
	while (sz(topsort)) {
		int v = topsort.front(); topsort.pop();
		depth[to[v]] = max(depth[to[v]],depth[v]+1);
		in_deg[to[v]]--;
		if (!in_deg[to[v]]) {topsort.push(to[v]);}
	}
	for (int x=1; x<=n; x++)
		for (int y=1; y<=m; y++)
			if (g[x][y] && in_deg[x*m+y])
				depth[x*m+y] = inf;
	
	//micro
	int cp = 0, pp = 1;
	gg[0].resize(n+5); gg[1].resize(n+5);gg[0][0].resize(m+5);
	gg[0][n+1].resize(m+5);gg[1][0].resize(m+5);gg[1][n+1].resize(m+5);
	for (int i=1; i<=n; i++) {
		gg[0][i].resize(m+5);
		gg[1][i].resize(m+5);
		for (int j=1; j<=m; j++) if (g[i][j]) gg[cp][i][j] = i*m+j;
	}
	
	fill(kil,kil+mxn,inf);
	
//	memset(kil,0x3f,sizeof(kil));
	
	for (int i=0; i<k; i++) {
		swap(cp,pp);
		for (int x=1; x<=n; x++) 
			for (int y=1; y<=m; y++) 
				gg[cp][x][y] = 0;
		for (int x=1; x<=n; x++)
			for (int y=1; y<=m; y++) {
				if (!gg[pp][x][y]) continue;
				if (s[i]=='U') {
					if (g[x-1][y]) {
						if (gg[cp][x-1][y]) {
							if (depth[gg[pp][x][y]] > depth[gg[cp][x-1][y]]) {swap(gg[pp][x][y],gg[cp][x-1][y]);}
							kil[gg[pp][x][y]] = i;
						} else gg[cp][x-1][y] = gg[pp][x][y];
					} else {
						if (gg[cp][x][y]) {
							if (depth[gg[pp][x][y]] > depth[gg[cp][x][y]]) {swap(gg[pp][x][y],gg[cp][x][y]);}
							kil[gg[pp][x][y]] = i;
						} else gg[cp][x][y] = gg[pp][x][y];
					}
				} else if (s[i]=='D') {
					if (g[x+1][y]) {
						if (gg[cp][x+1][y]) {
							if (depth[gg[pp][x][y]] > depth[gg[cp][x+1][y]]) {swap(gg[pp][x][y],gg[cp][x+1][y]);}
							kil[gg[pp][x][y]] = i;
						} else gg[cp][x+1][y] = gg[pp][x][y];
					} else {
						if (gg[cp][x][y]) {
							if (depth[gg[pp][x][y]] > depth[gg[cp][x][y]]) {swap(gg[pp][x][y],gg[cp][x][y]);}
							kil[gg[pp][x][y]] = i;
						} else gg[cp][x][y] = gg[pp][x][y];
					}
				} else if (s[i]=='L') {
					if (g[x][y-1]) {
						if (gg[cp][x][y-1]) {
							if (depth[gg[pp][x][y]] > depth[gg[cp][x][y-1]]) {swap(gg[pp][x][y],gg[cp][x][y-1]);}
							kil[gg[pp][x][y]] = i;
						} else gg[cp][x][y-1] = gg[pp][x][y];
					} else {
						if (gg[cp][x][y]) {
							if (depth[gg[pp][x][y]] > depth[gg[cp][x][y]]) {swap(gg[pp][x][y],gg[cp][x][y]);}
							kil[gg[pp][x][y]] = i;
						} else gg[cp][x][y] = gg[pp][x][y];
					}
				} else if (s[i]=='R') {
					if (g[x][y+1]) {
						if (gg[cp][x][y+1]) {
							if (depth[gg[pp][x][y]] > depth[gg[cp][x][y+1]]) {swap(gg[pp][x][y],gg[cp][x][y+1]);}
							kil[gg[pp][x][y]] = i;
						} else gg[cp][x][y+1] = gg[pp][x][y];
					} else {
						if (gg[cp][x][y]) {
							if (depth[gg[pp][x][y]] > depth[gg[cp][x][y]]) {swap(gg[pp][x][y],gg[cp][x][y]);}
							kil[gg[pp][x][y]] = i;
						} else gg[cp][x][y] = gg[pp][x][y];
					}
				}
			}
	}
	
	if (n==5)
	for (int x=1; x<=n; x++) {
		for (int y=1; y<=m; y++) {
			if (gg[cp][x][y]==164178) {
				cout<<x<<" "<<y<<"\n";
				cout<<to[164178]<<"\n";
			}
		}
	}
	
	cout<<"~~"<<to[164187]<<"\n\n";
	
	for (int x=1; x<=n; x++)
		for (int y=1; y<=m; y++)
			if (g[x][y] && sz(adj[x*m+y]))
				iter_order.push_back({depth[x*m+y],x,y});
	
	vector<int> kill_times;
	
	sort(all(iter_order));
	for (auto [D,X,Y] : iter_order) {
		int lock = adj[X*m+Y][0];
		for (int i : adj[X*m+Y]) {
			if (depth[i] > depth[lock]) lock = i;
		}
		for (int i : adj[X*m+Y]) {
			if (i==lock) continue;
			for (int j=0; j<depth[i]; j++) {
				kill_times.push_back(kil[i]+j*k+1);
				if (kil[i]+j*k+1==1000000001) {
					cout<<i<<": "<<depth[i]<<" "<<sz(adj[i])<<"\n";
					cout<<D<<" "<<X<<" "<<Y<<": "<<X*m+Y<<"\n\n";
				}
			}
		}
	}
	
	if (n==5) return 0;
	
	sort(all(kill_times));
	reverse(all(kill_times));
	
	int cn = cnt;
	while (sz(kill_times)) {
		int t = kill_times.back();
		ans[--cn] = t;
		kill_times.pop_back();
	}
	for (int i=1; i<cn; i++) ans[i] = -1;
	for (int i=1; i<=m*n; i++) {
		cout<<ans[i]<<"\n";
	}
	
}

/*
bad:
4,4178
*/