#include "bits/stdc++.h"
#include "rainbow.h"
using namespace std;
int r, c, sx, sy, m;
string s;
int lx, ly, rx, ry;
vector<pair<int,int>> g, ex, ey, two;
struct wavelet{
int n;
vector<vector<int>> vec, cnt;
vector<int> X, Y;
wavelet(){
}
void init(vector<pair<int,int>> v){
n=v.size();
vec.resize(4*n);
cnt.resize(4*n);
for(auto p:v) X.push_back(p.first), Y.push_back(p.second);
sort(X.begin(), X.end());
sort(Y.begin(), Y.end());
Y.erase(unique(Y.begin(), Y.end()), Y.end());
sort(v.begin(), v.end());
for(auto p:v){
vec[0].push_back(lower_bound(Y.begin(), Y.end(), p.second)-Y.begin());
}
build(0, 0, Y.size());
}
void build(int x, int l, int r){
if(r<=l+1) return;
int m=(l+r)/2;
cnt[x].resize(vec[x].size());
for(int i=0; i<vec[x].size(); i++){
cnt[x][i]=(i?cnt[x][i-1]:0)+(vec[x][i]<m);
vec[2*x+1+(vec[x][i]>=m)].push_back(vec[x][i]);
}
build(2*x+1, l, m);
build(2*x+2, m, r);
}
int query(int x, int l, int r, int li, int ri, int a, int b){ // ind [l,r] vals [a,b)
if(l>=a && r<=b) return ri-li+1;
if(l>=b || r<=a || ri<li) return 0;
int m=(l+r)/2;
int left_li=cnt[x][li]-(vec[x][li]<m);
int left_ri=cnt[x][ri]-1;
int right_li=li-cnt[x][li]+(vec[x][li]<m);
int right_ri=ri-cnt[x][ri];
return query(2*x+1, l, m, left_li, left_ri, a, b) + query(2*x+2, m, r, right_li, right_ri, a, b);
}
int rect(int a, int c, int b, int d){
if(b<a || d<c) return 0;
a=lower_bound(X.begin(), X.end(), a)-X.begin();
b=upper_bound(X.begin(), X.end(), b)-X.begin()-1;
c=lower_bound(Y.begin(), Y.end(), c)-Y.begin();
d=upper_bound(Y.begin(), Y.end(), d)-Y.begin();
return query(0, 0, Y.size(), a, b, c, d);
}
};
wavelet w_ex, w_ey, w_g, w_two;
int dx[]={0, 0, 1, 1};
int dy[]={0, 1, 0, 1};
void init(int R, int C, int sr, int sc, int M, char *S) {
s=S;
int x=sr, y=sc;
lx=rx=x;
ly=ry=y;
map<pair<int,int>,bool> mp;
g.push_back({x,y});
mp[{x,y}]=1;
for(char c:s){
if(c=='N') x--;
if(c=='S') x++;
if(c=='W') y--;
if(c=='E') y++;
g.push_back({x,y});
mp[{x,y}]=1;
lx=min(lx, x);
rx=max(rx, x);
ly=min(ly, y);
ry=max(ry, y);
}
sort(g.begin(), g.end());
g.erase(unique(g.begin(), g.end()), g.end());
for(auto p:g){
int x=p.first, y=p.second;
for(int k=0; k<4; k++){
x+=dx[k]; y+=dy[k];
if(mp[{x,y-1}] || mp[{x-1,y}] || mp[{x-1,y-1}] || mp[{x,y}]) two.push_back({x,y});
if(mp[{x-1, y}] || mp[{x,y}]) ex.push_back({x,y});
if(mp[{x, y-1}] || mp[{x,y}]) ey.push_back({x,y});
x-=dx[k]; y-=dy[k];
}
}
sort(ex.begin(), ex.end());
sort(ey.begin(), ey.end());
sort(two.begin(), two.end());
ex.erase(unique(ex.begin(), ex.end()), ex.end());
ey.erase(unique(ey.begin(), ey.end()), ey.end());
two.erase(unique(two.begin(), two.end()), two.end());
w_ex.init(ex);
w_ey.init(ey);
w_g.init(g);
w_two.init(two);
}
int colour(int ar, int ac, int br, int bc) {
int V=(br-ar+1)*(bc-ac+1)-w_g.rect(ar, ac, br, bc);
int E=(br-ar+1)*(bc-ac)+(br-ar)*(bc-ac+1)-w_ex.rect(ar+1,ac,br,bc)-w_ey.rect(ar,ac+1,br,bc);
int F=(br-ar)*(bc-ac)-w_two.rect(ar+1,ac+1,br,bc)+(ar<lx&&br>rx&&ac<ly&&bc>ry);
// cout << V << "-" << E << "+" << F<< '\n';
return V-E+F;
}
// add 1 face if rectangles covers region!
