\(O(NMA)\) で以下を列挙できます。

• 任意の \((x, y, i, t)\) について、\((x, y)\) から開始して、命令列 \(S_i\) の先頭 \(t ~ (0 \le t \le L_i)\) 文字を処理したときの位置 \((x', y')\)

これは、異なる \(S_i\) ごとに、すべてのマスを始点として愚直なシミュレーションをすればよいです。以下簡単のためこの写像を \((x', y') = f_t(x, y)\) と書きます。（以下 \(i\) は基本的に自明なので省略します）

さて、上記が得られたあとの各 \(i\) ごとの問題を考えます。 \(T = p \times L + q ~ (0 \le q \lt L)\) を用いれば、\(T\) ターン後の位置は以下のように求められます。

• \((R', C') = {f_{L}}^p(R, C)\) （ \(L\) 文字処理するを \(p\) 回繰り返したもの）を求める。
• \(f_q(R', C')\) を求める。（これが答え）

\(2\) つ目は前計算から \(O(1)\) で求める事ができますから、\(1\) つ目の求め方を考えましょう。

単純な関数の合成ですから、ダブリングを用いることができます。すなわち \(\displaystyle {f_L}^{2^k}\) を各マスについて前計算することを考えれば、 \(O(NM \log T)\) の前計算とクエリあたり \(O(\log T)\) で求めることができます。

また、遷移先が \(NM\) 個しか無いことから、それより短い周期が存在することを利用して、\(O(NM)\) の前計算とクエリあたり \(O(1)\) で求めることもできます。

計算量は、前者であれば \(O(NMA + NM|\mathcal S| \log T + K \log T)\) 、後者であれば \(O(NMA + K)\) です。

実装例（前者の方針で、かつメモリ削減のためダブリングテーブルを陽に管理せず、必要な箇所だけ計算しています）

from collections import defaultdict

n, m, k, t = map(int, input().split())
g = [input().strip() for _ in range(n)]

to = {c : list(range(n * m)) for c in "UDLR"}
for r in range(n):
    for c in range(m):
        if g[r][c] == '#': continue
        v = r * m + c
        if r > 0   and g[r-1][c] == '.': to['U'][v] = v-m
        if r+1 < n and g[r+1][c] == '.': to['D'][v] = v+m
        if c > 0   and g[r][c-1] == '.': to['L'][v] = v-1
        if c+1 < m and g[r][c+1] == '.': to['R'][v] = v+1

rob = defaultdict(list)
for i in range(k):
    r, c, _, s = input().split()
    rob[s].append(((int(r) - 1) * m + int(c) - 1, i))

ans = [0] * k

for s, qs in rob.items():
    p, q = divmod(t, len(s))

    f = list(range(n * m))
    for i, c in enumerate(s):
        if i == q:
            fq = f[:]
        f = [to[c][v] for v in f]
    while p:
        if p & 1:
            qs = [(f[v], i) for v, i in qs]
        f = [f[v] for v in f]
        p >>= 1

    for v, i in qs:
        ans[i] = fq[v]

for v in ans:
    print(v // m + 1, v % m + 1)