#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);
}
};
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 + 1 && ac < minY && bc > maxY + 1) {
C += 1;
}
return V + C - E;
}
