# 数据范围

$m,n,Q \leq 10^5,t_i \leq 10^{15}$

# 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL q=0;char ch=' ';
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') q=q*10+(LL)(ch-'0'),ch=getchar();
return q;
}
const int N=100005;
int n,m,Q,tot;
struct node{int x,y,l,r,bj,id;}a[N<<1];
int X1[N],Y1[N],X2[N],Y2[N],X0[N],Y0[N];char arr[N],gt[N];
int nxt[N<<1][50],c[N<<2];LL dis[N<<1][50],ti[N];//17

void build(int s,int t,int i) {
c[i]=0;if(s==t) return;
int mid=(s+t)>>1;
build(s,mid,i<<1),build(mid+1,t,(i<<1)|1);
}
void pd(int i) {c[i<<1]=c[(i<<1)|1]=c[i],c[i]=0;}
void chan(int l,int r,int s,int t,int i,int num) {
if(l<=s&&t<=r) {c[i]=num;return;}
int mid=(s+t)>>1;
if(c[i]) pd(i);
if(l<=mid) chan(l,r,s,mid,i<<1,num);
if(mid+1<=r) chan(l,r,mid+1,t,(i<<1)|1,num);
if(c[i<<1]==c[(i<<1)|1]) c[i]=c[i<<1];
}
int query(int x,int s,int t,int i) {
if(c[i]||s==t) return c[i];
int mid=(s+t)>>1;
if(x<=mid) return query(x,s,mid,i<<1);
else return query(x,mid+1,t,(i<<1)|1);
}

int cmp(node s1,node s2) {return s1.x==s2.x?s1.bj<s2.bj:s1.x<s2.x;}
void solve() {
sort(a+1,a+1+tot,cmp),build(1,m,1);
for(int i=1;i<=tot;++i)
if(a[i].bj==0) chan(a[i].l,a[i].r,1,m,1,a[i].id);
else nxt[a[i].id][0]=query(a[i].y,1,m,1);
}
void workL() {//朝左的箭头
tot=0;
for(int i=1;i<=n;++i)
if(arr[i]=='L') a[++tot]=(node){X1[i],Y1[i],0,0,1,i};
else a[++tot]=(node){X1[i],0,min(Y1[i],Y2[i]),max(Y1[i],Y2[i]),0,i};
for(int i=1;i<=Q;++i)
if(gt[i]=='L') a[++tot]=(node){X0[i],Y0[i],0,0,1,i+n};
solve();
}
void workR() {//朝右的箭头
tot=0;
for(int i=1;i<=n;++i)
if(arr[i]=='R') a[++tot]=(node){-X1[i],Y1[i],0,0,1,i};
else a[++tot]=(node){-X1[i],0,min(Y1[i],Y2[i]),max(Y1[i],Y2[i]),0,i};
//将所有的 x 坐标取相反数，相当于从大到小排序，节省代码量
for(int i=1;i<=Q;++i)
if(gt[i]=='R') a[++tot]=(node){-X0[i],Y0[i],0,0,1,i+n};
solve();
}
void workD() {//朝下的箭头
tot=0;
for(int i=1;i<=n;++i)
if(arr[i]=='D') a[++tot]=(node){Y1[i],X1[i],0,0,1,i};
else a[++tot]=(node){Y1[i],0,min(X1[i],X2[i]),max(X1[i],X2[i]),0,i};
//将关键词 x 和关键词 y 交换一下，也是减小代码量的
for(int i=1;i<=Q;++i)
if(gt[i]=='D') a[++tot]=(node){Y0[i],X0[i],0,0,1,i+n};
solve();
}
void workU() {//朝上的箭头
tot=0;
for(int i=1;i<=n;++i)
if(arr[i]=='U') a[++tot]=(node){-Y1[i],X1[i],0,0,1,i};
else a[++tot]=(node){-Y1[i],0,min(X1[i],X2[i]),max(X1[i],X2[i]),0,i};
for(int i=1;i<=Q;++i)
if(gt[i]=='U') a[++tot]=(node){-Y0[i],X0[i],0,0,1,i+n};
solve();
}

void pre() {
for(int i=1;i<=n;++i)
if(nxt[i][0])
dis[i][0]=abs(Y2[nxt[i][0]]-Y2[i])+abs(X2[nxt[i][0]]-X2[i]);
for(int i=1;i<=Q;++i)
if(nxt[i+n][0])
dis[i+n][0]=abs(Y2[nxt[i+n][0]]-Y0[i])+abs(X2[nxt[i+n][0]]-X0[i]);
for(int j=1;j<=49;++j)//伟大的倍增
for(int i=1;i<=n+Q;++i)
nxt[i][j]=nxt[nxt[i][j-1]][j-1],dis[i][j]=dis[i][j-1]+dis[nxt[i][j-1]][j-1];
}
void print(char fx,LL tt,LL x,LL y) {
if(fx=='L') printf("%lld %lld\n",max(1LL,x-tt)-1,y-1);
else if(fx=='R') printf("%lld %lld\n",min((LL)m,x+tt)-1,y-1);
else if(fx=='D') printf("%lld %lld\n",x-1,max(1LL,y-tt)-1);
else printf("%lld %lld\n",x-1,min((LL)m,y+tt)-1);
}
void walk() {
int kx,ky,to,kjl;
for(int i=1;i<=Q;++i) {
if(!nxt[i+n][0]) {print(gt[i],ti[i],X0[i],Y0[i]);continue;}
int now=i+n;LL tt=ti[i];
for(int j=49;j>=0;--j)
if(tt>=dis[now][j]&&nxt[now][j]) tt-=dis[now][j],now=nxt[now][j];
if(!nxt[now][0]) {print(arr[now],tt,X2[now],Y2[now]);continue;}
char ch=(now<=n?arr[now]:gt[now-n]);
int x1=(now<=n?X1[now]:X0[now-n]),x2=(now<=n?X2[now]:X0[now-n]);
int y1=(now<=n?Y1[now]:Y0[now-n]),y2=(now<=n?Y2[now]:Y0[now-n]);
to=nxt[now][0];
if(now>n&&x1>=min(X1[to],X2[to])&&x1<=max(X1[to],X2[to])
&&y1>=min(Y1[to],Y2[to])&&y1<=max(Y1[to],Y2[to])) kx=x1,ky=y1;//特判人本来就在箭头上
else if(ch=='L') ky=y1,kx=max(X1[to],X2[to]);
else if(ch=='R') ky=y1,kx=min(X1[to],X2[to]);
else if(ch=='D') kx=x1,ky=max(Y1[to],Y2[to]);
else kx=x1,ky=min(Y1[to],Y2[to]);//寻找当前箭头走到下一箭头，落到的位置
kjl=abs(kx-x2)+abs(ky-y2);//走到下一箭头要走的时间
if(kjl>tt) print(ch,tt,x2,y2);
else print(arr[to],tt-kjl,kx,ky);//还可以沿着下一箭头走
}
}
int main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
for(int i=1;i<=n;++i) {
if(Y1[i]==Y2[i]&&X1[i]>X2[i]) arr[i]='L';
else if(Y1[i]==Y2[i]&&X1[i]<X2[i]) arr[i]='R';
else if(X1[i]==X2[i]&&Y1[i]>Y2[i]) arr[i]='D';
else arr[i]='U';
}
for(int i=1;i<=Q;++i)
workL(),workR(),workD(),workU(),pre(),walk();
return 0;
}