#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
struct Fenwick {
int n;
vector<vector<int> > ys;
vector<vector<long long> > f;
vector<int> nn;
bool built;
void fake_add(int x, int y) {
assert(!built);
for (int i = x + 1; i <= n; i += i & -i) {
ys[i].emplace_back(y);
}
}
void build() {
assert(!built);
for (int i = 0; i <= n; ++i) {
sort(ys[i].begin(), ys[i].end());
ys[i].resize(unique(ys[i].begin(), ys[i].end()) - ys[i].begin());
nn[i] = ys[i].size();
f[i].resize(nn[i] + 1);
}
built = true;
}
void add(int x, int y) {
assert(built);
for (int i = x + 1; i <= n; i += i & -i) {
for (int j = lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin() + 1; j <= nn[i]; j += j & -j) {
f[i][j] += 1;
}
}
}
long long get(int x, int y) {
assert(built);
long long res = 0;
for (int i = x; i > 0; i -= i & -i) {
for (int j = lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin(); j > 0; j -= j & -j) {
res += f[i][j];
}
}
return res;
}
long long get(int x1, int y1, int x2, int y2) {
return get(x2, y2) - get(x1, y2) - get(x2, y1) + get(x1, y1);
}
Fenwick(int n = 0) : n(n), ys(n + 1), f(n + 1), nn(n + 1), built(false) {}
};
int n, m;
int k;
vector<pair<int, int> > a;
Fenwick fv, fex, fey, ff;
int mnx, mny, mxx, mxy;
bool blocked(int x, int y) {
const auto p = make_pair(x, y);
auto it = lower_bound(a.begin(), a.end(), p);
return it != a.end() && *it == p;
}
void init(int R, int C, int sr, int sc, int M, char *S) {
n = R;
m = C;
int x = sr - 1, y = sc - 1;
a.emplace_back(x, y);
for (int i = 0; i < M; ++i) {
if (S[i] == 'N') {
--x;
}
if (S[i] == 'S') {
++x;
}
if (S[i] == 'E') {
++y;
}
if (S[i] == 'W') {
--y;
}
a.emplace_back(x, y);
}
sort(a.begin(), a.end());
a.resize(unique(a.begin(), a.end()) - a.begin());
mnx = numeric_limits<int>::max();
mxx = numeric_limits<int>::min();
mny = numeric_limits<int>::max();
mxy = numeric_limits<int>::min();
vector<pair<int, int>> v, ex, ey, f;
for (const auto &[x, y] : a) {
mnx = min(mnx, x);
mxx = max(mxx, x);
mny = min(mny, y);
mxy = max(mxy, y);
v.emplace_back(x, y);
ex.emplace_back(x, y);
ey.emplace_back(x, y);
f.emplace_back(x, y);
if (x > 0) {
ex.emplace_back(x - 1, y);
f.emplace_back(x - 1, y);
}
if (y > 0) {
ey.emplace_back(x, y - 1);
f.emplace_back(x, y - 1);
}
if (x > 0 && y > 0) {
f.emplace_back(x - 1, y - 1);
}
}
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
sort(ex.begin(), ex.end());
ex.resize(unique(ex.begin(), ex.end()) - ex.begin());
sort(ey.begin(), ey.end());
ey.resize(unique(ey.begin(), ey.end()) - ey.begin());
sort(f.begin(), f.end());
f.resize(unique(f.begin(), f.end()) - f.begin());
fv = {n};
fex = {n};
fey = {n};
ff = {n};
for (const auto &[x, y] : v) {
fv.fake_add(x, y);
}
for (const auto &[x, y] : ex) {
fex.fake_add(x, y);
}
for (const auto &[x, y] : ey) {
fey.fake_add(x, y);
}
for (const auto &[x, y] : f) {
ff.fake_add(x, y);
}
fv.build();
fex.build();
fey.build();
ff.build();
for (const auto &[x, y] : v) {
fv.add(x, y);
}
for (const auto &[x, y] : ex) {
fex.add(x, y);
}
for (const auto &[x, y] : ey) {
fey.add(x, y);
}
for (const auto &[x, y] : f) {
ff.add(x, y);
}
}
int colour(int ar, int ac, int br, int bc) {
int x1 = ar - 1, y1 = ac - 1, x2 = br, y2 = bc;
long long v = (long long) (x2 - x1) * (y2 - y1) - fv.get(x1, y1, x2, y2);
long long e = (long long) (x2 - x1 - 1) * (y2 - y1) - fex.get(x1, y1, x2 - 1, y2) + (long long) (x2 - x1) * (y2 - y1 - 1) - fey.get(x1, y1, x2, y2 - 1);
long long f = (long long) (x2 - x1 - 1) * (y2 - y1 - 1) - ff.get(x1, y1, x2 - 1, y2 - 1) + (mnx > x1 && mny > y1 && mxx < x2 - 1 && mxy < y2 - 1);
if (v == 0) {
return 0;
}
long long c = f - e + v;
return (int) c;
}
