#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define pf printf
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
int N=200005;
struct node{
int s,e,m;
vector<int> v;
node *l,*r;
node(int _s,int _e){
s=_s;e=_e;m=(s+e)/2;
if(s!=e)l=new node(s,m),r=new node(m+1,e);
}
void up(int x,int nv){
if(s==x&&e==x){v.pb(nv);return;}
if(x<=m)l->up(x,nv);
else r->up(x,nv);
}
void init(){
if(s!=e)l->init(),r->init();
else{disc(v);return;}
v.resize(sz(l->v)+sz(r->v));
merge(all(l->v),all(r->v),v.begin());
}
ll qry(int x,int y,int a,int b){
if(x>y||a>b)return 0;
if(s==x&&e==y)return upper_bound(all(v),b)-lower_bound(all(v),a);
if(y<=m)return l->qry(x,y,a,b);
if(x>m)return r->qry(x,y,a,b);
return l->qry(x,m,a,b)+r->qry(m+1,y,a,b);
}
}*vertices,*horizontal,*vertical,*faces;
void addRiver(int r,int c){
vertices->up(r,c);
horizontal->up(r,c-1);horizontal->up(r,c);
vertical->up(r-1,c);vertical->up(r,c);
faces->up(r-1,c-1);faces->up(r,c-1);faces->up(r-1,c);faces->up(r,c);
}
void init(int R,int C,int sr,int sc,int M,char *S){
vertices=new node(0,N);
horizontal=new node(0,N);
vertical=new node(0,N);
faces=new node(0,N);
addRiver(sr,sc);
for(int i=0;i<M;++i){
if(S[i]=='N')--sr;
if(S[i]=='S')++sr;
if(S[i]=='W')--sc;
if(S[i]=='E')++sc;
addRiver(sr,sc);
}
vertices->init();
horizontal->init();
vertical->init();
faces->init();
}
int colour(int t,int l,int b,int r){
ll h=b-t+1,w=r-l+1;
ll v=h*w-vertices->qry(t,b,l,r);
ll e=(w-1)*h-horizontal->qry(t,b,l,r-1)+(h-1)*w-vertical->qry(t,b-1,l,r);
ll f=(h-1)*(w-1)-faces->qry(t,b-1,l,r-1);
if(vertices->qry(t+1,b-1,l+1,r-1)==vertices->qry(0,N,0,N))++f;
return v-e+f;
}
