#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;
struct segtreeee{
set<int> st[200100];
int rt[200100],CC;
struct nod{
int v,lc,rc;
} seg[1<<24];
void ins(int a,int b){
st[a].insert(b);
}
void upd(int &i,int l,int r,int p){
seg[++CC]=seg[i];
i=CC;
seg[i].v++;
if(l==r) return;
if(p<=l+r>>1)upd(seg[i].lc,l,l+r>>1,p);
else upd(seg[i].rc,l+r+2>>1,r,p);
}
void dostuf(){
for(int i=1;i<=2e5;i++){
rt[i]=rt[i-1];
for(auto j:st[i])
upd(rt[i],1,2e5,j);
}
}
int query(int i,int l,int r,int ll,int rr){
if(!i)return 0;
if(ll<=l&&r<=rr)
return seg[i].v;
if(ll>r||l>rr)
return 0;
return query(seg[i].lc,l,l+r>>1,ll,rr)+
query(seg[i].rc,l+r+2>>1,r,ll,rr);
}
int calc(int l1,int r1,int l2,int r2){
return query(rt[r1],1,2e5,l2,r2)-query(rt[l1-1],1,2e5,l2,r2);
}
} V,EH,EV,riv;
int bot,lef,rit,top;
void add_river(int x, int y) {
V.ins(x, y);
V.ins(x + 1, y);
V.ins(x, y + 1);
V.ins(x + 1, y + 1);
EH.ins(x, y);
EH.ins(x + 1, y);
EV.ins(x, y);
EV.ins(x, y + 1);
riv.ins(x, y);
}
void init(int R, int C, int sr, int sc, int M, char *S) {
add_river(sr, sc);
bot = top = sr;
lef = rit = 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--;
add_river(sr, sc);
bot = max(bot, sr);
top = min(top, sr);
lef = max(lef, sc);
rit = min(rit, sc);
}
V.dostuf();
EH.dostuf();
EV.dostuf();
riv.dostuf();
}
int colour(int ar, int ac, int br, int bc) {
int E = EH.calc(ar + 1, br, ac, bc) +
EV.calc(ar, br, ac + 1, bc);
int v = V.calc(ar + 1, br, ac + 1, bc);
int R = riv.calc(ar, br, ac, bc);
int C = (ar >= top || br <= bot || ac >= rit || bc <= lef ? 1 : 2);
return E - v + C - R;
}
