#include <bits/stdc++.h>
using namespace std;
const int S = 4100000;
const int N = 210000;
struct segtree {
struct node {
int s, l, r;
node(int s, int l, int r) : s(s), l(l), r(r) {}
node() {s = l = r = 0;}
node copy() {return {s, l, r};}
};
node vv[S];
int rr[N], last;
set<int> st[N];
segtree() {
last = 0;
}
void add(int r, int c) {
st[r].insert(c);
}
void build() {
for (int i = 1; i < N; i++) {
rr[i] = rr[i - 1];
for (int j : st[i])
upd(rr[i], 1, N - 1, j);
}
}
void upd(int &v, int l, int r, int k) {
last++;
vv[last] = vv[v].copy();
v = last;
vv[v].s++;
if (l == r) return;
int mid = (l + r) / 2;
if (k <= mid) upd(vv[v].l, l, mid, k);
else upd(vv[v].r, mid + 1, r, k);
}
int get(int &v, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return vv[v].s;
int mid = (l + r) / 2;
return get(vv[v].l, l, mid, ql, qr) + get(vv[v].r, mid + 1, r, ql, qr);
}
int get(int ar, int br, int ac, int bc) {
if (br < ar || bc < ac) return 0;
return get(rr[br], 1, N - 1, ac, bc) - get(rr[ar - 1], 1, N - 1, ac, bc);
}
};
segtree cells, verts, edgesv, edgesh;
// cells - obv
// verts - (i, j) is left top corner of (i, j) cell
// edgesv - (i, j) is left edge of (i, j) cell
// edgesh - (i, j) is top edge of (i, j) cell
int minr, maxr, minc, maxc;
void add(int r, int c) {
cells.add(r, c);
verts.add(r, c);
verts.add(r, c + 1);
verts.add(r + 1, c);
verts.add(r + 1, c + 1);
edgesv.add(r, c);
edgesv.add(r, c + 1);
edgesh.add(r, c);
edgesh.add(r + 1, c);
}
void init(int R, int C, int sr, int sc, int M, char *S) {
minr = maxr = sr;
minc = maxc = sc;
add(sr, sc);
for (int i = 0; i < M; i++) {
if (S[i] == 'N') sr--;
if (S[i] == 'S') sr++;
if (S[i] == 'W') sc--;
if (S[i] == 'E') sc++;
assert(1 <= sr && sr <= R && 1 <= sc && sc <= C);
add(sr, sc);
minr = min(minr, sr);
maxr = max(maxr, sr);
minc = min(minc, sc);
maxc = max(maxc, sc);
}
cells.build();
verts.build();
edgesv.build();
edgesh.build();
}
int colour(int ar, int ac, int br, int bc) {
int C = 1;
if (ar < minr && ac < minc && br > maxr && bc > maxc)
C++;
int B = cells.get(ar, br, ac, bc);
int V = verts.get(ar + 1, br, ac + 1, bc);
int E = edgesv.get(ar, br, ac + 1, bc) + edgesh.get(ar + 1, br, ac, bc);
return C - V + E - B;
}
