#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+20;
struct BIT2d{
int n;
vector<pair<int, int>> t[N];
void init(int _n){
n=_n;
for (int i=1; i<=n; ++i) t[i].emplace_back(-1, 0);
}
void fake_update(int x, int y){
for (int i=x; i<=n; i+=i&(-i)) t[i].emplace_back(y, 0);
}
void compress(){
for (int i=1; i<=n; ++i){
sort(t[i].begin(), t[i].end());
t[i].resize(unique(t[i].begin(), t[i].end())-t[i].begin());
}
}
void update(int x, int y, int val){
for (int i=x; i<=n; i+=i&(-i)){
for (int j=lower_bound(t[i].begin(), t[i].end(), make_pair(y, (int)1e9))-t[i].begin()-1; j<(int)t[i].size(); j+=j&(-j)){
t[i][j].second+=val;
}
}
}
int get(int x, int y){
int ans=0;
for (int i=x; i; i-=i&(-i)){
for (int j=lower_bound(t[i].begin(), t[i].end(), make_pair(y, (int)1e9))-t[i].begin()-1; j; j-=j&(-j)){
ans+=t[i][j].second;
}
}
return ans;
}
int get(int x, int y, int z, int t){
if (x>z || y>t) return 0;
return get(z, t)-get(z, y-1)-get(x-1, t)+get(x-1, y-1);
}
} bit1, bit2, bit3, bit4;
const int dx[]={1, -1, 0, 0}, dy[]={0, 0, 1, -1};
int r, c;
void init(int R, int C, int sr, int sc, int M, char *S) {
r=R, c=C;
bit1.init(r);
bit2.init(r+1);
bit3.init(r+1);
bit4.init(r);
set<pair<int, int>> st1, st2, st3, st4;
auto insert2=[&](int x, int y){
st2.emplace(x, y);
st2.emplace(x, y+1);
st2.emplace(x+1, y);
st2.emplace(x+1, y+1);
};
auto insert3=[&](int x, int y){
st3.emplace(x, y);
st3.emplace(x+1, y);
};
auto insert4=[&](int x, int y){
st4.emplace(x, y);
st4.emplace(x, y+1);
};
auto insert=[&](int x, int y){
st1.emplace(x, y);
insert2(x, y);
insert3(x, y);
insert4(x, y);
};
insert(sr, sc);
for (int i=0; i<M; ++i){
if (S[i]=='N') --sr;
if (S[i]=='S') ++sr;
if (S[i]=='E') ++sc;
if (S[i]=='W') --sc;
insert(sr, sc);
}
for (auto &i:st1) bit1.fake_update(i.first, i.second);
for (auto &i:st2) bit2.fake_update(i.first, i.second);
for (auto &i:st3) bit3.fake_update(i.first, i.second);
for (auto &i:st4) bit4.fake_update(i.first, i.second);
bit1.compress();
bit2.compress();
bit3.compress();
bit4.compress();
for (auto &i:st1) bit1.update(i.first, i.second, 1);
for (auto &i:st2) bit2.update(i.first, i.second, 1);
for (auto &i:st3) bit3.update(i.first, i.second, 1);
for (auto &i:st4) bit4.update(i.first, i.second, 1);
}
int colour(int ar, int ac, int br, int bc) {
int V=(br-ar+1)*2+(bc-ac+1)*2+bit2.get(ar+1, ac+1, br, bc);
int E=(br-ar+1)*2+(bc-ac+1)*2+bit3.get(ar+1, ac, br, bc)+bit4.get(ar, ac+1, br, bc);
int CC=1;
int cnt_out;
if (ar==br || ac==bc) cnt_out=bit1.get(ar, ac, br, bc);
else cnt_out=bit1.get(ar, ac, ar, bc-1)+bit1.get(ar, bc, br-1, bc)+bit1.get(br, ac+1, br, bc)+bit1.get(ar+1, ac, br, ac);
int cnt_in=bit1.get(ar+1, ac+1, br-1, bc-1);
if (cnt_in && !cnt_out) ++CC;
int F=cnt_in+cnt_out;
// cerr << V << ' ' << E << ' ' << CC << ' ' << F << '\n';
return E-V+CC-F;
}
