#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
int r,c;
#define fi first
#define se second
typedef pair<int,int> pii;
struct node {
node *L = NULL,*R=NULL;
int val = 0;
node(){};
node(int v){val = v;}
node(node *_L,node *_R){
L = _L;
R = _R;
val = ((L==NULL)?0:L->val) + ((R==NULL)?0:R->val);
}
};
const int MAXN = 2e5;
struct seg{
vector<node*>root;
vector<set<int>>d;
void add(int x,int y){d[x].insert(y);}
int r,c;
seg(){}
seg(int _r,int _c){
r = _r;
c = _c;
root.resize(r+1);
d.resize(r+1);
root[0] = new node();
}
node* upd(node *v,int l,int r,int pos){
if(l == r)return new node(v->val+1);
int tm = (l+r)/2;
if(pos <=tm){
if(v->L == NULL)v->L = new node();
return new node(upd(v->L,l,tm,pos), v->R);
}else{
if(v->R == NULL)v->R = new node();
return new node(v->L, upd(v->R,tm+1,r,pos));
}
}
int query(node *b,int l,int r,int tl,int tr){
if(l>r || !b)return 0;
if(l==tl && r==tr)return b->val;
int tm = (tl+tr)/2;
return query(b->L,l,min(r,tm),tl,tm)+query(b->R,max(l,tm+1),r,tm+1,tr);
}
int query(int xl,int xr,int yl,int yr){
if(xl > xr)return 0;
return query(root[xr],yl,yr,1,c) - query(root[xl-1],yl,yr,1,c);
}
void build(){
for(int i=1;i<=r;i++){
root[i] = new node(root[i-1]->L,root[i-1]->R);
for(int x:d[i])root[i] = upd(root[i],1,c,x);
}
}
}river,hedge,vedge,vert;
pii mx = {-1e9,-1e9};
pii mn = {1e9,1e9};
void init(int R, int C, int sr, int sc, int M, char *S) {
r = R;
c = C;
river = seg(r,c);
hedge = seg(r+1,c);
vedge = seg(r,c+1);
vert = seg(r+1,c+1);
int x = sr;
int y = sc;
river.add(x,y);
hedge.add(x,y);
hedge.add(x+1,y);
vedge.add(x,y);
vedge.add(x,y+1);
vert.add(x,y);
vert.add(x+1,y);
vert.add(x,y+1);
vert.add(x+1,y+1);
mx.fi = max(mx.fi,x);
mx.se = max(mx.se,y);
mn.fi = min(mn.fi,x);
mn.se = min(mn.se,y);
for(int i=0;i<M;i++){
char c = S[i];
if(c =='N')x--;
if(c =='S')x++;
if(c =='W')y--;
if(c =='E')y++;
river.add(x,y);
hedge.add(x,y);
hedge.add(x+1,y);
vedge.add(x,y);
vedge.add(x,y+1);
vert.add(x,y);
vert.add(x+1,y);
vert.add(x,y+1);
vert.add(x+1,y+1);
mx.fi = max(mx.fi,x);
mx.se = max(mx.se,y);
mn.fi = min(mn.fi,x);
mn.se = min(mn.se,y);
}
river.build();
vert.build();
hedge.build();
vedge.build();
}
int colour(int ar, int ac, int br, int bc) {
int C = (!(mn.fi <= ar || mn.se <= ac || mx.fi >= br || mx.se >= bc)) + 1;
int A = river.query(ar,br,ac,bc);
int V = vert.query(ar+1,br,ac+1,bc);
int E = hedge.query(ar+1,br,ac,bc) + vedge.query(ar,br,ac+1,bc);
//cout<<E<<" "<<V<<" "<<A<<" "<<C<<'\n';
int F = 1+C+E-V;
return F - A - 1;
}
