#include "rainbow.h"
#include <bits/stdc++.h>
#define forf(i,a,b) for(int i = a; i<=b; i++)
using namespace std;
typedef long long ll;
int minr,maxr,minc,maxc;
struct Node{
int v,l,r;
} def = {0,0,0};
struct ST{
int row,col;
vector<set<int> > S;
vector<int> T;
vector<int> root = {0};
vector<Node> node = {def};
void update(int now, int prv, int s, int e, int f, int x){
if(s==e){node[now].v = node[prv].v+x; return;}
int m = s+e>>1;
if(f<=m){
node[now].l = node.size(); node.push_back(def);
node[now].r = node[prv].r;
update(node[now].l,node[prv].l,s,m,f,x);
}
else{
node[now].r = node.size(); node.push_back(def);
node[now].l = node[prv].l;
update(node[now].r,node[prv].r,m+1,e,f,x);
}
node[now].v = node[node[now].l].v + node[node[now].r].v;
}
int query(int now , int prv, int s, int e,int l ,int r){
if(l<=s && e<=r) return node[now].v-node[prv].v;
if(r<s || l>e) return 0;
int m = s+e>>1;
return query(node[now].l,node[prv].l,s,m,l,r)+query(node[now].r,node[prv].r,m+1,e,l,r);
}
void init(int R, int C){
row = R+1;
col = C+1;
S.resize(row+1);
T.resize(row+1);
}
void add(int R, int C){
if(S[R].find(C) == S[R].end()) S[R].insert(C);
}
void process(){
int now = 0;
forf(i,1,row){
for(int j : S[i]){
now++;
root.push_back(node.size());
node.push_back(def);
update(root[now],root[now-1],1,col,j,1);
}
T[i] = now;
}
}
int query(int r1, int c1, int r2, int c2){
int now = T[r2];
int prv = T[r1-1];
return query(root[now],root[prv],1,col,c1,c2);
}
} F,V,Ex,Ey;
void mark(int row, int col){
F.add(row,col);
V.add(row,col); V.add(row+1,col); V.add(row,col+1); V.add(row+1,col+1);
Ex.add(row,col);Ex.add(row+1,col);
Ey.add(row,col); Ey.add(row,col+1);
}
void init(int R, int C, int sr, int sc, int M, char *S) {
int r,c;
r=R;c=C;
F.init(r,c);V.init(r,c);Ex.init(r,c);Ey.init(r,c);
int row = sr, col =sc;
minr = row; maxr = row; minc = col; maxc = col;
mark(row,col);
forf(i,0,M-1){
if(S[i] == 'N') row--;
if(S[i] == 'S') row++;
if(S[i] == 'E') col++;
if(S[i] == 'W') col--;
mark(row,col);
minr = min(minr,row); maxr = max(maxr,row);
minc = min(minc,col); maxc = max(maxc,col);
}
F.process();V.process();Ex.process();Ey.process();
}
int colour(int ar, int ac, int br, int bc) {
int f = F.query(ar,ac,br,bc);
int v = V.query(ar+1,ac+1,br,bc);
int ex = Ex.query(ar+1,ac,br,bc);
int ey = Ey.query(ar,ac+1,br,bc);
int p = 0;
if(ar<minr && br>maxr && ac<minc && bc>maxc) p = 1;
return 1-v+ex+ey-f+p;
}
