#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
int r,c;
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define pb push_back
typedef pair<int,int> pii;
const int MAXN = 2e5;
struct fen{
vector<vector<int>>bit;
vector<set<int>>data;
int r,c;
fen(){}
fen(int _r,int _c){
r = _r;
c = _c;
bit.resize(r+1);
data.resize(r+1);
}
void add(int x,int y){
data[x].insert(y);
}
int query(int x,int l,int r){
int res = 0;
for(int i=x;i;i-=i&(-i)){
int p = lower_bound(all(bit[i]),l) - bit[i].begin();
int q = upper_bound(all(bit[i]),r) - bit[i].begin();
res+=q-p;
}
return res;
}
int query(int xl,int xr,int yl,int yr){
if(xl > xr)return 0;
return query(xr,yl,yr) - query(xl-1,yl,yr);
}
void build(){
for(int i=1;i<=r;i++){
for(int j=i;j<=r;j+=j&(-j)){
for(int x:data[i])bit[j].pb(x);
}
}
for(int i=1;i<=r;i++)sort(all(bit[i]));
}
}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 = fen(r,c);
hedge = fen(r+1,c);
vedge = fen(r,c+1);
vert = fen(r+1,c+1);
int x = sr;
int y = sc;
for(int i=-1;i<M;i++){
if(i>=0){
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;
}
