#ifndef davele
#include "rainbow.h"
#endif // davele
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
#define vi vector <int>
#define pq priority_queue
#define MASK(i) (1ll<<(i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define x0 ___x0
#define y0 ___y0
#define div ___div
#define next ___next
#define prev ___prev
#define left ___left
#define right ___right
#define pos pisosi
#define pb push_back
#define pf push_front
using namespace std;
//const int mod = ;
//void add (int &a, const int&b){
// a+=b;
// if (a>=mod) a-=mod;
//}
//
//void sub (int&a, const int&b){
// a-=b;
// if (a<0) a+=mod;
//}
//
//void mul (int&a, const int&b){
// a*=b;
// a%=mod;
//}
template<class X, class Y>
bool minimize(X &x, const Y&y){
if (x<=y) return false;
else{
x = y;
return true;
}
}
template<class X, class Y>
bool maximize (X &x, const Y&y){
if (x>=y) return false;
else{
x = y;
return true;
}
}
/////////////////////////////////////////////////////////////////////////////////
//// dang nhap ham
//#ifndef davele
//
//#endif // davele
//
//// chay thu ham main:
//
//#ifdef davele
//
//#endif // davele
////////////////////////////////////////////////////////////////////////////
const ll lim = 200000, limit = lim+5;
vi pos_cnt[limit], pos_vertices[limit], pos_hor[limit], pos_lan[limit];
vi bit_cnt[limit], bit_vertices[limit], bit_hor[limit], bit_lan[limit];
ll n, m, q, sx, sy, len;
string s;
vector <pii> ele, vertices, hor, lan;
unordered_map <ll, unordered_map <ll, bool> > vis, vis_vertices, vis_hor, vis_lan;
ll dx[4] = {-1, -1, 0, 0};
ll dy[4] = {-1, 0, -1, 0};
void fakeupdate (vi pos[], ll x, ll y){
while (x<=lim){
pos[x].pb(y);
x += (x&(-x));
}
}
void compress(vi pos[], vi BIT[]){
for (ll i=1; i<=lim; i++){
pos[i].pb(0);
sort(pos[i].begin(), pos[i].end());
pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());
BIT[i].assign(pos[i].size(), 0);
}
}
void update (vi pos[], vi BIT[], ll x, ll y){
for (ll i = x; i<=lim; i+=(i&(-i))){
BIT[i][lower_bound(pos[i].begin(), pos[i].end(), y)-pos[i].begin()]++;
}
}
void fin (vi BIT[]){
for (ll i=1; i<=lim; i++){
for (int j=1; j<BIT[i].size(); j++) BIT[i][j]+=BIT[i][j-1];
}
}
ll get (vi pos[], vi BIT[], ll x, ll y){
ll ret = 0;
for (ll i=x; i>0; i&=i-1){
auto st = upper_bound(pos[i].begin(), pos[i].end(), y);
st--;
ret += BIT[i][st-pos[i].begin()];
}
// cerr<<" "<<ret<<"\n";
return ret;
}
void dfs (ll u, ll v, ll pos){
if (!vis[u][v]){
fakeupdate(pos_cnt, u, v);
ele.pb({u, v});
vis[u][v] = true;
for (ll i=0; i<4; i++){
ll x = u +dx[i], y = v+dy[i];
if (x>=1 && y>=1 && x<=n && y<=m && !vis_vertices[x][y]){
// cerr<<x<<" "<<y<<"\n";
fakeupdate(pos_vertices, x, y);
vertices.pb({x, y});
vis_vertices[x][y] = true;
}
}
for (ll i=-1; i<=0; i++){
ll x = u+i, y = v;
if (x>=1 && y>=1 && x<=n && y<=m && !vis_lan[x][y]){
fakeupdate(pos_lan, x, y);
lan.pb({x, y});
vis_lan[x][y] = true;
}
x = u; y = v+i;
if (x>=1 && y>=1 && x<=n && y<=m && !vis_hor[x][y]){
fakeupdate(pos_hor, x, y);
hor.pb({x, y});
vis_hor[x][y] = true;
}
}
}
vis[u][v] = true;
if (pos==len) return;
if (s[pos]=='N') dfs(u-1, v, pos+1);
else if (s[pos]=='S') dfs(u+1, v, pos+1);
else if (s[pos]=='E') dfs(u, v+1, pos+1);
else dfs(u, v-1, pos+1);
}
ll get_range (vi pos[], vi bit[], ll xl, ll yl, ll xr, ll yr){
return get(pos, bit, xr, yr) - get(pos, bit, xl-1, yr) - get(pos, bit, xr, yl-1) + get(pos, bit,xl-1, yl-1);
}
void init(int _n, int _m, int _sx, int _sy, int _len, char *S) {
n = _n;
m = _m;
sx = _sx;
sy = _sy;
len = _len;
s = S;
dfs (sx, sy, 0);
compress(pos_vertices, bit_vertices);
compress(pos_cnt, bit_cnt);
compress(pos_hor, bit_hor);
compress(pos_lan, bit_lan);
//
for (pii x:ele) update (pos_cnt, bit_cnt, x.fi, x.se);
for (pii x:vertices) update (pos_vertices, bit_vertices, x.fi, x.se);
for (pii x:hor) update (pos_hor, bit_hor, x.fi, x.se);
for (pii x:lan) update (pos_lan, bit_lan, x.fi, x.se);
//
fin(bit_vertices);
fin(bit_cnt);
fin(bit_hor);
fin(bit_lan);
}
int colour(int xl, int yl, int xr, int yr) {
ll nodes = (xr>xl && yr>yl) ? get_range (pos_vertices, bit_vertices, xl, yl, xr-1, yr-1) : 0;
ll edges = 0;
if (xr>xl) edges+=get_range(pos_lan, bit_lan, xl, yl, xr-1, yr);
if (yr>yl) edges+=get_range(pos_hor, bit_hor, xl, yl, xr, yr-1);
ll tplt = 1;
// nodes += 2*(xr-xl+yr-yl+2);
// edges += 2*(xr-xl+yr-yl+2);
// cerr<<" "<<edges<<" "<<nodes<<" "<<tplt<<"\n";
int cnttotal = get_range(pos_cnt, bit_cnt, xl, yl, xr, yr);
int cntmid =0;
if (xl+2<=xr && yl+2<=yr) cntmid = get_range(pos_cnt, bit_cnt, xl+1, yl+1, xr-1, yr-1);
//
if (cntmid==cnttotal && nodes>=1) tplt++;
//
ll tmp = edges-nodes+tplt-cnttotal;
if (tmp<0) assert(0==1);
return tmp;
}
