#include <bits/stdc++.h>
#include <rainbow.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
ll min(const ll &a, const ll &b){
return (a < b) ? a : b;
}
ll max(const ll &a, const ll &b){
return (a > b) ? a : b;
}
const ll Mod = 1000000007;
const int maxR = 2e5 + 1;
int n;
struct bit2d{
vector <vector <int>> node, bit;
int sizee;
void set_size(int n){
node.resize(n + 1);
bit.resize(n + 1);
sizee = n;
}
void fakeUpdate(int x, int y){
for (; x <= sizee; x += x & -x){
node[x].pb(y);
}
}
void build(){
for (int x = 1; x <= sizee; ++x){
sort(node[x].begin(), node[x].end());
node[x].resize(unique(node[x].begin(), node[x].end()) - node[x].begin());
bit[x].resize(node[x].size() + 1);
}
}
void update(int x, int yy){
for (int i = x; i <= sizee; i += i & -i){
int y = upper_bound(node[i].begin(), node[i].end(), yy) - node[i].begin();
for (int j = y; j < bit[i].size(); j += j & -j){
++bit[i][j];
}
}
}
int get(int x, int yy){
int sum = 0;
for (int i = x; i > 0; i -= i & -i){
int y = upper_bound(node[i].begin(), node[i].end(), yy) - node[i].begin();
for (int j = y; j > 0; j -= j & -j){
sum += bit[i][j];
}
}
return sum;
}
int get(int x1, int y1, int x2, int y2){
if (x1 > x2 || y1 > y2) return 0;
return get(x2, y2) + get(x1 - 1, y1 - 1) - get(x2, y1 - 1) - get(x1 - 1, y2);
}
};
bit2d vertices, horizontal_edges, vertical_edges, rivers; //unique
set <pii> r, c, b, v;
void add(int i, int j){
b.insert({i, j});
r.insert({i, j});
r.insert({i + 1, j});
c.insert({i, j});
c.insert({i, j + 1});
v.insert({i, j});
v.insert({i + 1, j});
v.insert({i, j + 1});
v.insert({i + 1, j + 1});
}
int minr, maxr, minc, maxc;
void init(int R, int C, int sr, int sc, int M, char *s) {
rivers.set_size(R + 1);
horizontal_edges.set_size(R + 1);
vertical_edges.set_size(R + 1);
vertices.set_size(R + 1);
minr = maxr = sr; minc = maxc = sc;
add(sr, sc);
for (int i = 0; i < M; ++i){
if (s[i] == 'W') --sc;
if (s[i] == 'E') ++sc;
if (s[i] == 'N') --sr;
if (s[i] == 'S') ++sr;
add(sr, sc);
minr = min(minr, sr);
minc = min(minc, sc);
maxr = max(maxr, sr);
maxc = max(maxc, sc);
}
//get space to allocate and update
for (const auto &i: b){
rivers.fakeUpdate(i.fi, i.se);
}
for (const auto &i: r){
horizontal_edges.fakeUpdate(i.fi, i.se);
}
for (const auto &i: c){
vertical_edges.fakeUpdate(i.fi, i.se);
}
for (const auto &i: v){
vertices.fakeUpdate(i.fi, i.se);
}
rivers.build();
horizontal_edges.build();
vertical_edges.build();
vertices.build();
for (const auto &i: b){
rivers.update(i.fi, i.se);
}
for (const auto &i: r){
horizontal_edges.update(i.fi, i.se);
}
for (const auto &i: c){
vertical_edges.update(i.fi, i.se);
}
for (const auto &i: v){
vertices.update(i.fi, i.se);
}
}
//statement??? "colour" is supposed to be plural
int colour(int ar, int ac, int br, int bc){
int C = 1 + (ar < minr && br > maxr && ac < minc && bc > maxc);
int E = horizontal_edges.get(ar + 1, ac, br, bc) + vertical_edges.get(ar, ac + 1, br, bc);
int V = vertices.get(ar + 1, ac + 1, br, bc);
int R = rivers.get(ar, ac, br, bc);
return E + C - R - V;
}
