#include "rainbow.h"
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <map>
#define ll long long
using namespace std;
vector <array<ll, 2>> V;
map <array<ll, 2>, ll> mp, vert, edger, edgec;
string T = "NESW";
vector <ll> X[200001], VR[200001], ER[200001], EC[200001], G[200001];
ll x, y, r, c, nx, ny, tot, e, v, f, dj[4][2] = {0, 0, 0, 1, 1, 0, 1, 1}, dr[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};
struct SegTree2D{
vector <ll> st[800004];
void build(ll id, ll l, ll r) {
if (l == r) {
st[id] = X[l];
return;
}
ll mid = (l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
int i = 0, j = 0;
while (i < st[id*2].size() && j < st[id*2+1].size()) {
if (st[id*2][i] <= st[id*2+1][j]) st[id].push_back(st[id*2][i++]);
else st[id].push_back(st[id*2+1][j++]);
}
while (i < st[id*2].size()) st[id].push_back(st[id*2][i++]);
while (j < st[id*2+1].size()) st[id].push_back(st[id*2+1][j++]);
}
ll query(ll id, ll l, ll r, ll xl, ll xr, ll yl, ll yr) {
if (xr < l || r < xl || xl > xr || yl > yr) return 0;
else if (xl <= l && r <= xr) {
auto it = lower_bound(st[id].begin(), st[id].end(), yl);
auto it2 = lower_bound(st[id].begin(), st[id].end(), yr+1);
return (it2-st[id].begin())-(it-st[id].begin());
}
ll mid = (l+r)/2;
return query(id*2, l, mid, xl, xr, yl, yr) + query(id*2+1, mid+1, r, xl, xr, yl, yr);
}
}STV, STER, STEC, ST;
void init(int R, int C, int sr, int sc, int M, char *S) {
r = R, c = C;
mp.clear();
V.clear();
V.push_back({sr, sc});
x = sr, y = sc;
for (int j=0; j<M; ++j) {
auto u = S[j];
for (int i=0; i<4; ++i) {
if (u == T[i]) {
nx = x + dr[i][0], ny = y + dr[i][1];
x = nx, y = ny;
V.push_back({x, y});
break;
}
}
}
for (int i=0; i<V.size(); ++i) {
--V[i][0], --V[i][1];
x = V[i][0], y = V[i][1];
if (!mp.count({x, y})) ++mp[{x, y}];
for (int j=0; j<4; ++j) {
nx = x + dj[j][0], ny = y + dj[j][1];
++vert[{nx, ny}];
}
++edger[{x, y}];
++edger[{x+1, y}];
++edgec[{x, y}];
++edgec[{x, y+1}];
}
for (auto it = edger.begin(); it != edger.end();) {
auto nx = next(it);
auto [x, y] = it->first;
ER[x].push_back(y);
it = nx;
}
for (auto it = edgec.begin(); it != edgec.end();) {
auto nx = next(it);
auto [x, y] = it->first;
EC[y].push_back(x);
it = nx;
}
for (auto it = vert.begin(); it != vert.end();) {
auto nxt = next(it);
auto [x, y] = it->first;
VR[x].push_back(y);
it = nxt;
}
for (auto it = mp.begin(); it != mp.end();) {
auto nxt = next(it);
auto [x, y] = it->first;
G[x].push_back(y);
it = nxt;
}
for (int i=0; i<=R; ++i) {
sort(VR[i].begin(), VR[i].end());
sort(ER[i].begin(), ER[i].end());
}
for (int i=0; i<=C; ++i) {
sort(EC[i].begin(), EC[i].end());
}
for (int i=0; i<=R; ++i) swap(X[i], VR[i]);
STV.build(1, 0, R);
for (int i=0; i<=R; ++i) swap(X[i], ER[i]);
STER.build(1, 0, R);
for (int i=0; i<=C; ++i) swap(X[i], EC[i]);
STEC.build(1, 0, C);
for (int i=0; i<=R; ++i) swap(X[i], G[i]);
ST.build(1, 0, R);
}
int colour(int ar, int ac, int br, int bc) {
--ar, --ac;
e = STER.query(1, 0, r, ar+1, br-1, ac, bc-1) + STEC.query(1, 0, c, ac+1, bc-1, ar, br-1) + (br-ar+bc-ac) * 2;
v = STV.query(1, 0, r, ar+1, br-1, ac+1, bc-1) + (br-ar+bc-ac) * 2;
f = e-v+1;
return f-ST.query(1, 0, r, ar, br-1, ac, bc-1);
}
