#include "rainbow.h"
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
int readint(){
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
namespace perst{
int root[3][200005],son[5000005][2],sum[500005],tsz;
void modify(int&x,int f,int l,int r,int p,int v){
x=++tsz; son[x][0]=son[f][0]; son[x][1]=son[f][1]; sum[x]=sum[f]+v;
if(l==r) return;
int mid=(l+r)/2;
if(p<=mid) modify(son[x][0],son[f][0],l,mid,p,v);
else modify(son[x][1],son[f][1],mid+1,r,p,v);
}
void modify(int t,int x,int y,int v){modify(root[t][x],root[t][x],1,200000,y,v);}
int ask(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return sum[x];
int mid=(l+r)/2;
if(qr<=mid) return ask(son[x][0],l,mid,ql,qr);
else if(ql>mid) return ask(son[x][1],mid+1,r,ql,qr);
else return ask(son[x][0],l,mid,ql,qr)+ask(son[x][1],mid+1,r,ql,qr);
}
int query(int t,int x1,int x2,int y1,int y2){
if(x1>x2||y1>y2) return 0;
return ask(root[t][x2],1,200000,y1,y2)-ask(root[t][x1-1],1,200000,y1,y2);
}
};
int mat[55][55],lx,ly,rx,ry;
vector<int> qs[3][55];
void init(int r,int c,int sc,int sr,int m,char* s){
mat[sc][sr]=1;
lx=rx=sc;
ly=ry=sr;
qs[0][sc].pb(sr);
qs[1][sc].pb(sr);
qs[1][sc].pb(sr-1);
qs[2][sc].pb(sr);
qs[2][sc-1].pb(sr);
for(int i=0;i<m;i++){
if(s[i]=='N') sc--;
if(s[i]=='S') sc++;
if(s[i]=='E') sr++;
if(s[i]=='W') sr--;
mat[sc][sr]=1;
lx=min(lx,sc);
rx=max(rx,sc);
ly=min(ly,sr);
ry=max(ry,sr);
qs[0][sc].pb(sr);
qs[1][sc].pb(sr);
qs[1][sc].pb(sr-1);
qs[2][sc].pb(sr);
qs[2][sc-1].pb(sr);
}
for(int i=1;i<=r;i++){
for(int t=0;t<3;t++){
perst::root[t][i]=perst::root[t][i-1];
sort(qs[t][i].begin(),qs[t][i].end());
qs[t][i].erase(unique(qs[t][i].begin(),qs[t][i].end()),qs[t][i].end());
for(int j:qs[t][i]) if(1<=j&&j<=c) perst::modify(t,i,j,1);
}
}
}
int colour(int x1,int y1,int x2,int y2){
ll res=0;
if(x1<lx&&rx<x2&&y1<ly&&ry<y2) res=1;
res+=(x2-x1+1)*1ll*(y2-y1+1)-perst::query(0,x1,x2,y1,y2);
res-=(x2-x1+1)*1ll*(y2-y1)-perst::query(1,x1,x2,y1,y2-1);
res-=(x2-x1)*1ll*(y2-y1+1)-perst::query(2,x1,x2-1,y1,y2);
for(int i=x1;i<=x2;i++) for(int j=y1;j<=y2;j++){
if(mat[i][j]==1) continue;
if(i+1<=x2&&j+1<=y2&&mat[i+1][j]==0&&mat[i][j+1]==0&&mat[i+1][j+1]==0) res++;
}
return res;
}
