#include <bits/stdc++.h>
#include "rainbow.h"
using namespace std;
vector<pair<int,int>> pts;
struct segtr{
vector<int> t;
int n;
void init(int s){
n = s;
t.assign((s + 1) * 4,0);
}
void upd(int pos,int val,int v,int tl,int tr){
t[v] += val;
if(tl == tr){
return;
}
int tm = (tl + tr) >> 1;
if(pos <= tm) upd(pos,val,v+v,tl,tm);
else upd(pos,val,v+v+1,tm+1,tr);
}
int get(int l,int r,int v,int tl,int tr){
if(l > r || tl >r || l > tr) return 0;
if(tl >= l && tr <= r) return t[v];
int tm = (tl + tr) >> 1;
return get(l,r,v+v,tl,tm) + get(l,r,v+v+1,tm+1,tr);
}
};
struct dd{
vector<vector<int>> f,t;
vector<segtr> b;
int n;
void build(int v,int tl,int tr){
if(tl == tr){
t[v] = f[tl];
t[v].resize(unique(t[v].begin(),t[v].end()) - t[v].begin());
// cerr << (int)t[v].size() << '\n';
b[v].init((int)t[v].size());
}else{
int tm = (tl + tr) >> 1;
build(v+v,tl,tm);
build(v + v + 1,tm + 1,tr);
t[v].resize((int)t[v+v].size() + (int)t[v +v + 1].size());
merge(t[v + v].begin(),t[v + v].end(),t[v + v + 1].begin(),t[v + v + 1].end(),t[v].begin());
t[v].resize(unique(t[v].begin(),t[v].end()) - t[v].begin());
b[v].init((int)t[v].size());
}
}
void init(int s,vector<vector<int>> _f){
n = s;
t.resize((n + 1) * 4);
b.resize((n+1)*4);
f = _f;
build(1,1,n);
}
void upd(int x,int y,int val,int v,int tl,int tr){
int it = lower_bound(t[v].begin(),t[v].end(),y)-t[v].begin()+1;
b[v].upd(it,val,1,1,b[v].n);
if(tl == tr) return;
int tm = (tl + tr) >> 1;
if(x <= tm) upd(x,y,val,v+v,tl,tm);
else upd(x,y,val,v+v+1,tm+1,tr);
}
int get(int l,int r,int l1,int r1,int v,int tl,int tr){
// return 0;
if(l > r || tl > r || l > tr) return 0;
if(tl >= l && tr <= r){
int it = lower_bound(t[v].begin(),t[v].end(),l1)-t[v].begin()+1;
int it1 = upper_bound(t[v].begin(),t[v].end(),r1)-t[v].begin();
return b[v].get(it,it1,1,1,b[v].n);
}
int tm =(tl+tr)>>1;
return get(l,r,l1,r1,v+v,tl,tm)+get(l,r,l1,r1,v+v+1,tm+1,tr);
}
}ver,bf,uu,ll,d1,d2;
map<pair<int,int>,int>in;
void init(int R, int C, int sr, int sc, int M, char *S) {
pts.push_back({sr,sc});
vector<vector<int>> f(R+1);
in[{sr,sc}]=1;
for(int i = 0;i < M;i++){
if(S[i] == 'N'){
sr--;
}else if(S[i] == 'S'){
sr++;
}else if(S[i] == 'W'){
sc--;
}else{
sc++;
}
assert(sr <= R && sr >= 1);
assert(sc <= C && sc >= 1);
pts.push_back({sr,sc});
in[{sr,sc}]=1;
}
sort(pts.begin(),pts.end());
pts.resize(unique(pts.begin(),pts.end()) - pts.begin());
for(auto [x,y]:pts){
f[x].push_back(y);
}
ver.init(R,f);
bf.init(R,f);
uu.init(R,f);ll.init(R,f);
d1.init(R,f);d2.init(R,f);
for(auto [x,y]:pts){
if(in.count({x+1,y})&&in.count({x,y+1})&&in.count({x+1,y+1})){
bf.upd(x,y,1,1,1,bf.n);
}
if(in.count({x-1,y}))
{
uu.upd(x,y,1,1,1,uu.n);
}
if(in.count({x,y-1})){
ll.upd(x,y,1,1,1,ll.n);
}
if(in.count({x+1,y+1}) && !in.count({x+1,y}) && !in.count({x,y+1})){
d1.upd(x,y,1,1,1,uu.n);
}
if(in.count({x+1,y-1}) && !in.count({x+1,y}) && !in.count({x,y-1})){
d2.upd(x,y,1,1,1,uu.n);
}
ver.upd(x,y,1,1,1,ver.n);
}
}
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
map<pair<int,int>,bool> k,vis;
int colour(int ar, int ac, int br, int bc) {
k.clear();
vis.clear();
int E = 0;
for(auto [r,c]:pts){
if(r >= ar && r <= br && c >= ac && c <= bc){
k[{r,c}] = 1;
}
}
for(int i = ar - 1;i <= br + 1;i++){
k[{i,ac-1}] = k[{i,bc+1}] = 1;
}
for(int i = ac - 1;i <= bc + 1;i++){
k[{ar-1,i}] = k[{br+1,i}] = 1;
}
int _bf = 0,tt = 0;;
for(auto [xx,_y]:k){
auto [r,c] = xx;
// if(k.count({r+1,c+1}) && !k.count({r+1,c}) && !k.count({r,c+1})){
// E += 1;
// }
// if(k.count({r+1,c-1}) && !k.count({r+1,c}) && !k.count({r,c-1})){
// E += 1;
// }
}
int val =ver.get(ar,br,ac,bc,1,1,ver.n);
int bord_sum =(br-ar+3)*2+(bc-ac+1)*2;
bool ok = false;
int _ = ver.get(ar,ar,ac,bc,1,1,ver.n)+ver.get(ar,br,bc,bc,1,1,ver.n)+ver.get(ar,br,ac,ac,1,1,ver.n)+ver.get(br,br,ac,bc,1,1,ver.n);
if(val > 0 && _==0){
ok=1;
}
_bf = (in.count({ar,ac})) + (in.count({ar,bc}))+(in.count({br,ac})) + (in.count({br,bc})) + bf.get(ar,br-1,ac,bc-1,1,1,bf.n);
_bf += ll.get(ar,ar,ac+1,bc,1,1,ll.n)+ll.get(br,br,ac+1,bc,1,1,ll.n);
_bf += uu.get(ar+1,br,ac,ac,1,1,uu.n)+uu.get(ar+1,br,bc,bc,1,1,uu.n);
E += d1.get(ar,br-1,ac,bc-1,1,1,d1.n);
E += d2.get(ar,br-1,ac+1,bc,1,1,d2.n);
E += (ll.get(ar,br,ac+1,bc,1,1,ll.n) + uu.get(ar+1,br,ac,bc,1,1,uu.n)) + _;
return -val+ E - _bf + 1+ok;
}
