#include <bits/stdc++.h>
#include "rainbow.h"
template <class T>
using Vec = std::vector<T>;
// struct Count2D {
// int size;
// Vec<Vec<int>> pts;
// Vec<Vec<int>> left, right;
// Count2D() = default;
// Count2D(const int range) {
// size = 1;
// while (size < range) {
// size <<= 1;
// }
// pts.resize(2 * size);
// left.resize(size);
// right.resize(size);
// }
// void add(const int x, const int y) {
// pts[x + size].push_back(y);
// }
// void build() {
// for (int i = size; i < 2 * size; ++i) {
// std::sort(pts[i].begin(), pts[i].end());
// pts[i].erase(std::unique(pts[i].begin(), pts[i].end()), pts[i].end());
// }
// for (int i = size - 1; i > 0; --i) {
// const auto l = 2 * i;
// const auto r = 2 * i + 1;
// const auto l_sz = (int) pts[l].size();
// const auto r_sz = (int) pts[r].size();
// const auto sz = l_sz + r_sz;
// pts[i].reserve(sz);
// left[i].reserve(sz + 1);
// right[i].reserve(sz + 1);
// int s = 0, t = 0;
// while (s < l_sz || t < r_sz) {
// left[i].push_back(s);
// right[i].push_back(t);
// if (t == r_sz || (s < l_sz && pts[l][s] < pts[r][t])) {
// pts[i].push_back(pts[l][s]);
// s += 1;
// }
// else {
// pts[i].push_back(pts[r][t]);
// t += 1;
// }
// }
// left[i].push_back(l_sz);
// right[i].push_back(r_sz);
// }
// }
// int count(const int xl, const int xr, int yl, int yr) const {
// yl = std::lower_bound(pts[1].begin(), pts[1].end(), yl) - pts[1].begin();
// yr = std::lower_bound(pts[1].begin(), pts[1].end(), yr) - pts[1].begin();
// return count(xl, xr, yl, yr, 1, 0, size);
// }
// int count(const int xl, const int xr, const int yl, const int yr, const int k, const int l, const int r) const {
// if (xl <= l && r <= xr) {
// return yr - yl;
// }
// if (xr <= l || r <= xl) {
// return 0;
// }
// const auto m = (l + r) / 2;
// return count(xl, xr, left[k][yl], left[k][yr], 2 * k, l, m) + count(xl, xr, right[k][yl], right[k][yr], 2 * k + 1, m, r);
// }
// };
struct Count2D {
Count2D(const int _ = 0) { }
std::set<std::pair<int, int>> set;
void add(const int x, const int y) {
set.emplace(x, y);
}
void build() {
}
int count(const int xl, const int xr, const int yl, const int yr) const {
int ret = 0;
for (const auto [x, y]: set) {
if (xl <= x && x < xr && yl <= y && y < yr) {
ret += 1;
}
}
return ret;
}
};
int Row, Column;
int maxX, minX, maxY, minY;
Count2D vert, edgeR, edgeC, cycle;
void add(const int x, const int y) {
maxX = std::max(maxX, x);
minX = std::min(minX, x);
maxY = std::max(maxY, y);
minY = std::min(minY, y);
vert.add(x, y);
edgeR.add(x, y);
edgeC.add(x, y);
cycle.add(x, y);
if (x > 0) {
edgeC.add(x - 1, y);
cycle.add(x - 1, y);
}
if (y > 0) {
edgeR.add(x, y - 1);
cycle.add(x, y - 1);
}
if (x > 0 && y > 0) {
cycle.add(x - 1, y - 1);
}
}
void init(int R, int C, int sr, int sc, int M, char *S) {
Row = R;
Column = C;
maxX = -1, minX = R, maxY = -1, minY = C;
vert = Count2D(R);
edgeR = Count2D(R);
edgeC = Count2D(R);
cycle = Count2D(R);
sr -= 1;
sc -= 1;
add(sr, sc);
for (int i = 0; i < M; ++i) {
if (S[i] == 'N') sr -= 1;
if (S[i] == 'S') sr += 1;
if (S[i] == 'E') sc += 1;
if (S[i] == 'W') sc -= 1;
add(sr, sc);
}
vert.build();
edgeR.build();
edgeC.build();
cycle.build();
}
int colour(int ar, int ac, int br, int bc) {
ar -= 1;
ac -= 1;
long long V = 0, E = 0, C = 0;
V += (long long) (br - ar) * (bc - ac);
V -= vert.count(ar, br, ac, bc);
E += (long long) (br - ar) * (bc - ac - 1);
E -= edgeR.count(ar, br, ac, bc - 1);
E += (long long) (br - ar - 1) * (bc - ac);
E -= edgeC.count(ar, br - 1, ac, bc);
C += (long long) (br - ar - 1) * (bc - ac - 1);
C -= cycle.count(ar, br - 1, ac, bc - 1);
if (ar < minX && br >= maxX && ac < minY && bc >= maxY) {
C += 1;
}
return V + C - E;
}
