#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define all(aaa) aaa.begin(), aaa.end()
const int N = 2e5 + 5;
struct ST {
vector<pair<int, int>> pts;
vector<int> t[N * 4];
void init() {
if (!pts.empty()) {
sort(all(pts));
pts.erase(unique(all(pts)), pts.end());
build(1, 0, (int)pts.size() - 1);
}
}
void build(int v, int L, int R) {
if (L == R) {
t[v] = {pts[L].second};
}
else {
int m = (L + R) >> 1;
build(v * 2, L, m);
build(v * 2 + 1, m + 1, R);
merge(all(t[v * 2]), all(t[v * 2 + 1]), back_inserter(t[v]));
}
}
int que(int lx, int rx, int ly, int ry, int v, int L, int R) {
if (rx < pts[L].first || lx > pts[R].first)
return 0;
if (lx <= pts[L].first && pts[R].first <= rx) {
return upper_bound(all(t[v]), ry) - lower_bound(all(t[v]), ly);
}
int m = (L + R) >> 1;
return que(lx, rx, ly, ry, v * 2, L, m)
+ que(lx, rx, ly, ry, v * 2 + 1, m + 1, R);
}
int que(int lx, int rx, int ly, int ry) {
if (pts.empty())
return 0;
return que(lx, rx, ly, ry, 1, 0, pts.size() - 1);
}
} teh, tev, tf, tv;
string dir = "NSEW";
const int dx[4] = {-1, 1, 0, 0},
dy[4] = {0, 0, 1, -1},
sdx[4] = {1, 1, 0, 0},
sdy[4] = {0, 1, 0, 1};
int mnx, mny, mxx, mxy;
set<pair<int, int>> st;
void init(int R, int C, int sr, int sc, int M, char *S) {
mnx = sr;
mxx = sr;
mny = sc;
mxy = sc;
int x = sr, y = sc;
st.insert({x, y});
for (int i = 0; i < M; i++) {
int k = find(all(dir), S[i]) - dir.begin();
x += dx[k];
y += dy[k];
st.insert({x, y});
mnx = min(mnx, x);
mxx = max(mxx, x);
mny = min(mny, y);
mxy = max(mxy, y);
}
for (auto p : st) {
tf.pts.push_back(p);
tev.pts.push_back({p.first, p.second});
tev.pts.push_back({p.first - 1, p.second});
teh.pts.push_back({p.first, p.second});
teh.pts.push_back({p.first, p.second - 1});
for (int i = 0; i < 4; i++) {
tv.pts.push_back({p.first - sdx[i], p.second - sdy[i]});
}
}
tev.init();
teh.init();
tv.init();
tf.init();
}
int colour(int ar, int ac, int br, int bc) {
int ans = 1;
if (ar < mnx && mxx < br &&
ac < mny && mxy < bc) {
ans++;
}
ans += tev.que(ar, br - 1, ac, bc);
ans += teh.que(ar, br, ac, bc - 1);
ans -= tv.que(ar, br - 1, ac, bc - 1);
ans -= tf.que(ar, br, ac, bc);
return ans;
}
