#include <bits/stdc++.h>
using namespace std;
#define all(X) begin(X), end(X)
const int Z = 2e5+4;
template<const int n>
struct SegmentTree {
vector<int> a[2*n];
void insert(int i, int v) {
a[i+n].push_back(v);
}
void build() {
for(int i = n; i < 2*n; ++i) {
sort(all(a[i]));
a[i].erase(unique(all(a[i])), end(a[i]));
}
for(int i = n; --i; )
merge(all(a[2*i]), all(a[2*i+1]), back_inserter(a[i]));
}
int getCnt(int i, int lv, int rv) {
return upper_bound(all(a[i]), rv) - lower_bound(all(a[i]), lv);
}
int count(int l, int r, int lv, int rv) {
int x = 0;
for(l += n, r += n+1; l < r; l /= 2, r /= 2) {
if(l & 1) x += getCnt(l++, lv, rv);
if(r & 1) x += getCnt(--r, lv, rv);
}
return x;
}
};
SegmentTree<2*Z> edges;
SegmentTree<Z> cells, vertices;
int minR = Z, minC = Z, maxR, maxC;
void init(int R, int C, int uR, int uC, int M, char* S) {
for(int i = 0; i <= M; ++i) {
cells.insert(uC, uR);
minR = min(minR, uR);
minC = min(minC, uC);
maxR = max(maxR, uR);
maxC = max(maxC, uC);
for(int x : {0, 1}) for(int y : {0, 1}) {
vertices.insert(uC+x, uR+y);
}
for(int x : {0, 2}) {
edges.insert(2*uC+x, 2*uR+1);
edges.insert(2*uC+1, 2*uR+x);
}
if(i < M) {
S[i] == 'S' ? ++uR : 0;
S[i] == 'N' ? --uR : 0;
S[i] == 'E' ? ++uC : 0;
S[i] == 'W' ? --uC : 0;
}
}
edges.build();
cells.build();
vertices.build();
}
int colour(int ar, int ac, int br, int bc) {
bool add = ar < minR && ac < minC && br > maxR && bc > maxC;
return edges.count(2*ac+1, 2*bc+1, 2*ar+1, 2*br+1) - vertices.count(ac+1, bc, ar+1, br) - cells.count(ac, bc, ar, br) + 1 + add;
}
