import sys
from heapq import heapify, heappush, heappop
sys.setrecursionlimit(10**5)
dx = [1,0,-1,0]
dy = [0,1,0,-1]
inf = float('inf')
def solve():
# Input
H, W, K, sr, sc = map(int, input().split())
s = [[inf if j == '#' else 0 for j in input()] for i in range(H)]
N = int(input())
fd = dict()
for i in range(N):
fr, fc, F, D = map(int, input().split())
fd[(fr-1, fc-1)] = (F, D)
# Process
ans = []
ch = [s[i][:] for i in range(H)]
ch[sr-1][sc-1] = 1
inu2(H, W, K, 0, sr-1, sc-1, fd, ch, ans)
# Output
print(''.join(ans))
def inu2(H, W, K, t, a, b, fd, ch, ans):
if t == K:
return None
mxhp = []
i2c = ['D', 'R', 'U', 'L']
c, d = 0, 0
for i in range(4):
if ch[a + dx[i]][b + dy[i]] == 0 and (a + dx[i], b + dy[i]) in fd:
value = fd[(a + dx[i], b + dy[i])][0] - t * fd[(a + dx[i], b + dy[i])][1]
if value > 0:
heappush(mxhp, (-value, i))
else:
ch[a + dx[i]][b + dy[i]] = inf
if mxhp:
v, j = heappop(mxhp)
ans.append(i2c[j])
ch[a + dx[j]][b + dy[j]] += 1
c = a + dx[j]
d = b + dy[j]
else:
for i in range(4):
if ch[a+dx[i]][b+dy[i]] != inf:
heappush(mxhp, (ch[a+dx[i]][b+dy[i]], i))
if mxhp:
v, j = heappop(mxhp)
ans.append(i2c[j])
ch[a + dx[j]][b + dy[j]] += 1
c = a + dx[j]
d = b + dy[j]
else:
ans.append('-')
c, d = a, b
return inu2(H, W, K, t + 1, c, d, fd, ch, ans)
def inu1_oukyu(H, W, K, t, a, b, fd, ch, ans):
if t == K:
return None
elif t > K//2:
ans.append('-')
return inu1_oukyu(H, W, K, t + 1, a, b, fd, ch, ans)
mxhp = []
i2c = ['D', 'R', 'U', 'L']
c, d = 0, 0
for i in range(4):
if ch[a + dx[i]][b + dy[i]] == 0 and (a + dx[i], b + dy[i]) in fd:
value = fd[(a + dx[i], b + dy[i])][0] - t * fd[(a + dx[i], b + dy[i])][1]
if value > 0:
heappush(mxhp, (-value, i))
else:
ch[a + dx[i]][b + dy[i]] = inf
if mxhp:
v, j = heappop(mxhp)
ans.append(i2c[j])
ch[a + dx[j]][b + dy[j]] += 1
c = a + dx[j]
d = b + dy[j]
else:
for i in range(4):
if ch[a+dx[i]][b+dy[i]] != inf:
heappush(mxhp, (ch[a+dx[i]][b+dy[i]], i))
if mxhp:
v, j = heappop(mxhp)
ans.append(i2c[j])
ch[a + dx[j]][b + dy[j]] += 1
c = a + dx[j]
d = b + dy[j]
else:
ans.append('-')
c, d = a, b
return inu1_oukyu(H, W, K, t + 1, c, d, fd, ch, ans)
def debug(x, table):
for name, val in table.items():
if x is val:
print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
return None
if __name__ == '__main__':
solve()