#include "rainbow.h"
#include<iostream>
#include<set>
using namespace std;
const int N=2e5+831,TS=2e7+2004;
typedef long long ll;
int n,m;
set<int>v[N],e1[N],e2[N],f[N];
int sum[TS],lc[TS],rc[TS];
int rv[N],re1[N],re2[N],rf[N];//Red Velvet Wendy <3
int sz;
int mass;
void put(int sr,int sc){
for(int i=0; i<2 ;i++){
for(int j=0; j<2 ;j++) v[sr+i].insert(sc+j);
e1[sr].insert(sc+i);
e2[sr+i].insert(sc);
}
f[sr].insert(sc);
}
int ins(int id,int pos,int l,int r){
if(l==r){
sz++;
sum[sz]=sum[id]+1;
return sz;
}
int mid=(l+r)/2;
if(pos<=mid){
ins(lc[id],pos,l,mid);
sz++;
lc[sz]=sz-1;
rc[sz]=rc[id];
}
else{
ins(rc[id],pos,mid+1,r);
sz++;
lc[sz]=lc[id];
rc[sz]=sz-1;
}
sum[sz]=sum[lc[sz]]+sum[rc[sz]];
return sz;
}
int qr(int id,int l,int r,int ll,int rr){
if(r<ll || l>rr) return 0;
if(ll<=l && r<=rr) return sum[id];
int mid=(l+r)/2;
return qr(lc[id],l,mid,ll,rr)+qr(rc[id],mid+1,r,ll,rr);
}
int cnt(int id1,int id2,int l,int r){
return qr(id2,1,m+1,l,r)-qr(id1,1,m+1,l,r);
}
void init(int R, int C, int sr, int sc, int M, char *S){
n=R,m=C;
put(sr,sc);
for(int i=0; i<M ;i++){
if(S[i]=='N') sr--;
if(S[i]=='E') sc++;
if(S[i]=='S') sr++;
if(S[i]=='W') sc--;
put(sr,sc);
}
rv[0]=re1[0]=re2[0]=rf[0]=1;
sz=1;
for(int i=1; i<=n+1 ;i++){
rv[i]=rv[i-1],re1[i]=re1[i-1],re2[i]=re2[i-1],rf[i]=rf[i-1];
for(auto it=v[i].begin(); it!=v[i].end() ;++it) rv[i]=ins(rv[i],*it,1,m+1);
for(auto it=e1[i].begin(); it!=e1[i].end() ;++it) re1[i]=ins(re1[i],*it,1,m+1);
for(auto it=e2[i].begin(); it!=e2[i].end() ;++it) re2[i]=ins(re2[i],*it,1,m+1);
for(auto it=f[i].begin(); it!=f[i].end() ;++it) rf[i]=ins(rf[i],*it,1,m+1);
}
mass=cnt(rf[0],rf[n],1,m+1);
}
int colour(int ar, int ac, int br, int bc){
int v=(br-ar+bc-ac)*2+4+cnt(rv[ar],rv[br],ac+1,bc);
int e=(br-ar+bc-ac)*2+4+cnt(re1[ar-1],re1[br],ac+1,bc)+cnt(re2[ar],re2[br],ac,bc);
int f=cnt(rf[ar-1],rf[br],ac,bc);
if(ar+2<=br && ac+2<=bc && cnt(rf[ar],rf[br-1],ac+1,bc-1)==mass){
return 2+e-v-f;
}
return 1+e-v-f;
}
