- 首先有个很朴素的(dp)，设(f_{i,j,k})表示(k)时刻地点(i,j)的最长长度。
- 然后这样不能优化，考虑利用一段连续时间是同一个方向，设(f_{k,i,j})表示时段(k)，地点(i,j)的最长长度。
- 那么$$f_{k,i,j}=max(f_{k,i,j},f_{k,i,j}+dis)(i,j为上一个合理的位置)$$
- 如果中间有一个不合法位置直接退出（然而这样就过了……）
- 显然有限制(disleq len)，那么一个最大值(f_{k,i,j})所贡献的是一段区间，单调队列优化即可。
- 复杂度(O(k*n^2))
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define R register int
#define ll long long
using namespace std;
const int N=201;
int n,m,len,ox,oy,q,s,t,op,ans,f[N][N];char Mp[N][N];
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
int vl[N],id[N];
int gi(){
R x=0,k=1;char c=getchar();
while(c!='-'&&(c<'0'||c>'9'))c=getchar();
if(c=='-')k=-1,c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*k;
}
void sol(R x,R y){
R tl=0,hd=1;
for(R i=1;x>=1&&x<=n&&y>=1&&y<=m;++i,x+=dx[op],y+=dy[op]){
if(Mp[x][y]!='.')hd=1,tl=0;
else{
while(hd<=tl&&vl[tl]-id[tl]<=f[x][y]-i)tl--;
tl++,vl[tl]=f[x][y],id[tl]=i;
while(hd<=tl&&i-id[hd]>len)hd++;
f[x][y]=vl[hd]+i-id[hd],ans=max(ans,f[x][y]);
}
}
}
int main(){
n=gi(),m=gi(),ox=gi(),oy=gi(),q=gi();
for(R i=1;i<=n;++i)
for(R j=1;j<=m;++j)
cin>>Mp[i][j];
memset(f,-127,sizeof(f)),f[ox][oy]=0;
for(R i=1;i<=q;++i){
s=gi(),t=gi(),op=gi()-1,len=t-s+1;
if(op==0)for(R j=1;j<=m;++j)sol(n,j);
else if(op==1)for(R j=1;j<=m;++j)sol(1,j);
else if(op==2)for(R j=1;j<=n;++j)sol(j,m);
else for(R j=1;j<=n;++j)sol(j,1);
}
for(R i=1;i<=n;++i)
for(R j=1;j<=m;++j)
ans=max(ans,f[i][j]);
cout<<ans<<endl;
return 0;
}