#include <bits/stdc++.h>
#include "rainbow.h"
using namespace std;
const int MAXN = 2e6 + 25;
#define mid ((l + r) >> 1)
struct PersistentSegmentTree {
set <pair <int, int>> points;
const int L = 200000;
int tree[MAXN], tl[MAXN], tr[MAXN], cnt;
vector <pair <int, int>> roots;
int new_node (int x, int y, int z) {
++cnt; assert(cnt < MAXN); tl[cnt] = x; tr[cnt] = y;
tree[cnt] = z;
return cnt;
}
int build (int l, int r) {
if (l == r) {
cnt++; assert(cnt < MAXN);
return cnt;
}
int left = build(l, mid), right = build(mid + 1, r);
return new_node(left, right, 0);
}
int update (int l, int r, int a, int b, int node) {
if (l == r) {
int x = tree[node]; x += b;
cnt++; assert(cnt < MAXN);
tree[cnt] = x; return cnt;
}
if (a <= mid) {
int z = update(l, mid, a, b, tl[node]);
return new_node(z, tr[node], tree[z] + tree[tr[node]]);
} else {
int z = update(mid + 1, r, a, b, tr[node]);
return new_node(tl[node], z, tree[z] + tree[tl[node]]);
}
}
int get (int l, int r, int a, int b, int node) {
if (l > b || r < a) return 0;
if (l >= a && r <= b) return tree[node];
return get(l, mid, a, b, tl[node]) + get(mid + 1, r, a, b, tr[node]);
}
void init () {
cnt = 0;
int root = build(0, L);
int prev = -1;
for (auto [x, y] : points) {
int z = update(0, L, y, 1, root);
if (x != prev) {
roots.push_back({prev, root});
root = z; prev = x;
} else root = z;
}
roots.push_back({prev, root});
}
int getroot (int x) {
int l = 0, r = (int)roots.size() - 1, ans = -1;
while (l <= r) {
if (roots[mid].first <= x) {
ans = mid; l = mid + 1;
} else {
r = mid - 1;
}
}
return ans == -1 ? -1 : roots[ans].second;
}
int query (int a, int b, int c, int d) {
auto g = getroot(a - 1), h = getroot(c);
int ret = 0;
ret += get(0, L, b, d, h);
ret -= get(0, L, b, d, g);
return ret;
}
} cur[4];
typedef long long ll;
int dx[4] = {0, -1, 0, 1}, dy[4] = {1, 0, -1, 0};
int mny, mxy, mnx, mxx;
map <char, int> lk = {
{'E', 0},
{'N', 1},
{'W', 2},
{'S', 3}
};
int n, m;
set <pair <int, int>> badcells, badvertedges, badhoredges, badfaces;
void insert (int x, int y) {
if (badcells.count({x, y})) return;
badcells.insert({x, y});
if (y > 0 && !badhoredges.count({x, y - 1})) {
badhoredges.insert({x, y - 1});
}
if (x > 0 && !badvertedges.count({x - 1, y})) {
badvertedges.insert({x - 1, y});
}
if (y < m && !badhoredges.count({x, y})) {
badhoredges.insert({x, y});
}
if (x < n && !badvertedges.count({x, y})) {
badvertedges.insert({x, y});
}
if (y > 0 && x > 0 && !badfaces.count({x - 1, y - 1})) {
badfaces.insert({x - 1, y - 1});
}
if (y > 0 && x + 1 < n && !badfaces.count({x, y - 1})) {
badfaces.insert({x, y - 1});
}
if (y + 1 < m && x > 0 && !badfaces.count({x - 1, y})) {
badfaces.insert({x - 1, y});
}
if (y + 1 < m && x + 1 < n && !badfaces.count({x, y})) {
badfaces.insert({x, y});
}
}
void init (int N, int M, int x, int y, int z, char *s) {
n = N; m = M;
x--; y--;
mny = mxy = y; mnx = mxx = x;
insert(x, y);
for (int i = 0; i < z; i++) {
x += dx[lk[s[i]]]; y += dy[lk[s[i]]];
mny = min(mny, y);
mxy = max(mxy, y);
mnx = min(mnx, x);
mxx = max(mxx, x);
insert(x, y);
}
cur[0].points = badcells; cur[0].init();
cur[1].points = badvertedges; cur[1].init();
cur[2].points = badhoredges; cur[2].init();
cur[3].points = badfaces; cur[3].init();
}
ll querycell (int a, int b, int c, int d) {
return cur[0].query(a, b, c, d);
}
ll queryvert (int a, int b, int c, int d) {
return cur[1].query(a, b, c, d);
}
ll queryhor (int a, int b, int c, int d) {
return cur[2].query(a, b, c, d);
}
ll queryface (int a, int b, int c, int d) {
return cur[3].query(a, b, c, d);
}
int colour (int ar, int ac, int br, int bc) {
ar--; br--; ac--; bc--;
if (ar > br) swap(ar, br);
if (ac > bc) swap(ac, bc);
ll v = 0, e = 0, f = 0;
v = (br - ar + 1) * 1ll * (bc - ac + 1);
v -= querycell(ar, ac, br, bc);
ll e1 = (br - ar) * 1ll * (bc - ac + 1);
if (ar < br) e1 -= queryvert(ar, ac, br - 1, bc);
ll e2 = (br - ar + 1) * 1ll * (bc - ac);
if (ac < bc) e2 -= queryhor(ar, ac, br, bc - 1);
e = e1 + e2;
f = (br - ar) * 1ll * (bc - ac);
if (ar < br && ac < bc) f -= queryface(ar, ac, br - 1, bc - 1);
if (ar < mnx && br > mxx && ac < mny && bc > mxy) f++;
return v - e + f;
}
