#include<bits/stdc++.h>
#include "rainbow.h"
#define MAXN 200007
using namespace std;
const int maxs=2e5+7;
struct PST{
struct node{
int l,r;
int val;
};
int root[MAXN],last,num=1;
node tree[20*MAXN];
void upgrade(){
last++; root[last]=num;
}
int update(int v,int l,int r,int pos){
if(l==r){
num++;
tree[num].val=tree[v].val+1;
return num;
}else{
int tt=(l+r)/2;
int lt,rt;
if(pos<=tt){
lt=update(tree[v].l,l,tt,pos);
rt=tree[v].r;
}else{
lt=tree[v].l;
rt=update(tree[v].r,tt+1,r,pos);
}
num++;
tree[num].val=tree[lt].val+tree[rt].val;
tree[num].l=lt; tree[num].r=rt;
return num;
}
}
int getsum(int v1,int v2,int l,int r,int ll,int rr){
if(ll>rr)return 0;
if(l==ll and r==rr){
return tree[v2].val-tree[v1].val;
}else{
int tt=(l+r)/2;
return getsum(tree[v1].l,tree[v2].l,l,tt,ll,min(tt,rr)) + getsum(tree[v1].r,tree[v2].r,tt+1,r,max(tt+1,ll),rr);
}
}
void build(set< pair<int,int> > &s){
auto it=s.begin();
for(int i=1;i<=maxs;i++){
while(it!=s.end()){
pair<int,int> curr=*it;
if(curr.first==i)update(num,1,maxs,curr.second);
else break;
it++;
}
upgrade();
}
}
int query(int a,int c,int b,int d){
return getsum(root[a-1],root[c],1,maxs,b,d);
}
}rivers,vertices,edgesh,edgesv;
int n,m,x,y,minx,miny,maxx,maxy;
set< pair<int,int> > ver,eh,ev,riv;
void add(int x,int y){
ver.insert({x,y});
ver.insert({x+1,y});
ver.insert({x,y+1});
ver.insert({x+1,y+1});
riv.insert({x,y});
ev.insert({x,y});
ev.insert({x,y+1});
eh.insert({x,y});
eh.insert({x+1,y});
}
void init(int R, int C, int sr, int sc, int M, char *S) {
n=R; m=C;
x=sr; y=sc;
add(x,y);
minx=maxx=x;
miny=maxy=y;
for(int i=0;i<M;i++){
if(S[i]=='N')x--;
if(S[i]=='S')x++;
if(S[i]=='E')y++;
if(S[i]=='W')y--;
add(x,y);
minx=min(minx,x);
miny=min(miny,y);
maxx=max(maxx,x);
maxy=max(maxy,y);
}
rivers.build(riv);
edgesh.build(eh);
edgesv.build(ev);
vertices.build(ver);
}
int colour(int ar,int ac,int br,int bc){
int R=rivers.query(ar,br,ac,bc);
int V=vertices.query(ar+1,br,ac+1,bc) + 2*(bc-ac+2) + 2*(br-ar+2) - 4;
int E=edgesv.query(ar,br,ac+1,bc) + edgesh.query(ar+1,br,ac,bc) + 2*(bc-ac+1) + 2*(br-ar+1) ;
if(minx>ar and maxx<br and miny>ac and maxy<bc)E++;
return E-V-R+1;
}
/*int main(){
init(6, 4,3, 3, 9,"NWESSWEWS");
cout<<colour(2,3, 2, 3)<<"\n";
cout<<colour(3,2,4,4)<<"\n";
cout<<colour(5,3,6,4)<<"\n";
cout<<colour(1,2,5,3)<<"\n";
cout<<colour(1,1,6,4)<<":\n";
return 0;
}*/
