#include<bits/stdc++.h>
#define int long long
#define debug puts("fuck");
using namespace std;
struct querys{
	int towards,a,b;
}Q[200005];
struct node{
	int s,t,v,p;
}tree[800005][25]; 
void build(int now,int l,int r,int j){
	tree[now][j].s=l;
	tree[now][j].t=r;
	tree[now][j].p=0;
	tree[now][j].v=0;
	if(l==r)return;
	int mid=(l+r)/2;
	build(now*2,l,mid,j);
	build(now*2+1,mid+1,r,j);
}
void push_down(int now,int j){
	tree[now*2][j].p+=tree[now][j].p;
	tree[now*2][j].v+=tree[now][j].p;
	tree[now*2+1][j].p+=tree[now][j].p;
	tree[now*2+1][j].v+=tree[now][j].p;
	tree[now][j].p=0;
}
int query(int tgt,int now,int j){
	if(tree[now][j].s==tgt&&tree[now][j].t==tgt){
		return tree[now][j].v;
	}
	if(tree[now][j].t<tgt||tree[now][j].s>tgt){
		return 0;
	}
	if(tree[now][j].p)push_down(now,j);
	return query(tgt,now*2,j)+query(tgt,now*2+1,j);
;
}
void modify(int now,int l,int r,int j){
	if(tree[now][j].s>=l&&tree[now][j].t<=r){
		tree[now][j].p++;
		tree[now][j].v++;
		return;
	} 
	if(tree[now][j].t<l||tree[now][j].s>r){
		return;
	}
	if(tree[now][j].p)push_down(now,j);
	modify(now*2,l,r,j);
	modify(now*2+1,l,r,j);
} 
int n, m, q, k, nx = 1, ny = 1;
char mp[505][505];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mp[i][j];
        }
    }
    for (int i = 0; i < k; i++) {
        build(1, 0, n/k+1, i);
    }
    for (int i = 1; i <= q; i++) {
        char x;
        int y, z;
        cin >> x >> y >> z;
        if (x == 'U')
            Q[i].towards = 1;
        else if (x == 'D')
            Q[i].towards = 3;
        else if (x == 'L')
            Q[i].towards = 0;
        else
            Q[i].towards = 2;
        Q[i].a = y;
        Q[i].b = z;
    }
    for (int i = 1; i <= q; i++) {
//        for (int j = 1; j <= q; j++) {
//            cout << (Q[j].towards + 2 * query(j / k, 1, j % k)) % 4 << ' ';
//        }
//        cout << endl;
        int l=query(i / k, 1, i % k);
        if ((Q[i].towards + 2 * l) % 4 == 1) {
            nx = max(1ll, nx - Q[i].a);
        }
        else if ((Q[i].towards + 2 * l) % 4 == 0) {
            ny = max(1ll, ny - Q[i].a);
        }
        else if ((Q[i].towards + 2 * l) % 4 == 3) {
            nx = min(n, nx + Q[i].a);
        }
        else if ((Q[i].towards + 2 * l) % 4 == 2) {
            ny = min(m, ny + Q[i].a);
        }
        if (mp[nx][ny] == 'X') {
            modify(1, i / k + 1, i / k + Q[i].b, i % k);
        }
    }
    cout << nx << ' ' << ny;
    return 0;
}

思路：把询问按%k的值分类，然后用线段树区间修改和单点查询
因为只要求单点查询，所以这份代码只维护线段树的tag（即p），所以非叶子节点的val（即v）都是不正确的，s是节点的起点，t是节点的终点