#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct PST{
struct Node{
Node *lc, *rc;
int sum;
Node(int l, int r){
sum = 0;
if(l==r) lc = rc = nullptr;
else{
int m = (l+r)/2;
lc = new Node(l, m);
rc = new Node(m+1, r);
}
}
Node(Node *lc, Node *rc, int sum): lc(lc), rc(rc), sum(sum){}
~Node(){
if(lc) delete lc;
if(rc) delete rc;
}
int query(int l, int r, int s, int e){
if(r<s || e<l) return 0;
if(s<=l && r<=e) return sum;
int m = (l+r)>>1;
return lc->query(l, m, s, e) + rc->query(m+1, r, s, e);
}
Node* update(int l, int r, int x, int v){
if(l==r){
Node* tmp = new Node(lc, rc, sum + v);
return tmp;
}
int m = (l+r)>>1;
Node* tmp = new Node(lc, rc, sum+v);
if(x<=m) tmp->lc = lc->update(l, m, x, v);
else tmp->rc = rc->update(m+1, r, x, v);
return tmp;
}
} *root = nullptr;
int n;
PST(){}
Node *yHistory[200002];
int yMaximum;
void init(int _n){
n = _n;
root = new Node(0, n);
for(int i=0; i<=200001; i++) yHistory[i] = nullptr;
yMaximum = 0;
}
void update(int x, int y){
while(yMaximum < y) yHistory[yMaximum++] = root;
root = root->update(0, n, x, 1);
}
void finish(){
while(yMaximum < 200001) yHistory[yMaximum++] = root;
}
int query(int xl, int xr, int yl, int yr){
// printf("(%d - %d) = %d\n", yHistory[yr]->query(0, n, xl, xr), (yl == 0 ? 0 : yHistory[yl-1]->query(0, n, xl, xr)));
return yHistory[yr]->query(0, n, xl, xr) - (yl == 0 ? 0 : yHistory[yl-1]->query(0, n, xl, xr));
}
} vpst, ehpst, evpst, fpst;
struct Point{
int x, y;
Point(){}
Point(int x, int y): x(x), y(y){}
bool operator<(const Point &r)const{
if(y!=r.y) return y<r.y;
return x<r.x;
}
bool operator==(const Point &r)const{
return x==r.x && y==r.y;
}
};
int N, M;
int xMin = 1e9, xMax = -1e9, yMin = 1e9, yMax = -1e9;
vector<Point> vvec, ehvec, evvec, fvec;
void check(int X, int Y){
xMin = min(xMin, X), yMin = min(yMin, Y);
xMax = max(xMax, X), yMax = max(yMax, Y);
vvec.push_back(Point(X, Y));
if(Y!=1) ehvec.push_back(Point(X, Y-1));
if(Y!=M) ehvec.push_back(Point(X, Y));
if(X!=1) evvec.push_back(Point(X-1, Y));
if(X!=N) evvec.push_back(Point(X, Y));
if(Y!=1 && X!=1) fvec.push_back(Point(X-1, Y-1));
if(Y!=M && X!=1) fvec.push_back(Point(X-1, Y));
if(Y!=1 && X!=N) fvec.push_back(Point(X, Y-1));
if(Y!=M && X!=N) fvec.push_back(Point(X, Y));
}
void update(PST &pst, vector<Point> &vec){
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
pst.init(N);
for(Point p: vec){
pst.update(p.x, p.y);
}
pst.finish();
}
void init(int R, int C, int sr, int sc, int K, char *S){
N = R, M = C;
vpst.init(N);
ehpst.init(N);
evpst.init(N);
fpst.init(N);
int x = sr, y = sc;
check(x, y);
for(int i=0; i<K; i++){
if(S[i] == 'N') x--;
else if(S[i] == 'E') y++;
else if(S[i] == 'W') y--;
else x++;
check(x, y);
}
update(vpst, vvec);
update(ehpst, ehvec);
update(evpst, evvec);
update(fpst, fvec);
}
int colour(int x1, int y1, int x2, int y2){
ll V = ll(x2-x1+1) * ll(y2-y1+1) - vpst.query(x1, x2, y1, y2);
ll EH = ll(x2-x1+1) * ll(y2-y1) - ehpst.query(x1, x2, y1, y2-1);
ll EV = ll(x2-x1) * ll(y2-y1+1) - evpst.query(x1, x2-1, y1, y2);
ll F = ll(x2-x1) * ll(y2-y1) - fpst.query(x1, x2-1, y1, y2-1);
if(x1 < xMin && xMax < x2 && y1 < yMin && yMax < y2) F++;
// printf("%lld %lld %lld %lld\n", V, EH, EV, F);
return V-(EH+EV)+F;
}
