#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
struct rectSum {
private:
int n;
vector<pii> arr;
vector<vector<int>> vec;
vector<vector<int>> cl;
void build(int l, int r, int id) {
if(r-l == 1) {
vec[id].pb(arr[l].second);
return;
}
build(l, mid, lc);
build(mid, r, rc);
cl[id].pb(0);
int i=0, j=0;
while(i<SZ(vec[lc]) && j<SZ(vec[rc])) {
if(vec[lc][i]<=vec[rc][j]) {
vec[id].pb(vec[lc][i++]);
cl[id].pb(cl[id].back()+1);
}
else {
vec[id].pb(vec[rc][j++]);
cl[id].pb(cl[id].back());
}
}
while(i<SZ(vec[lc])) {
vec[id].pb(vec[lc][i++]);
cl[id].pb(cl[id].back()+1);
}
while(j<SZ(vec[rc])) {
vec[id].pb(vec[rc][j++]);
cl[id].pb(cl[id].back());
}
vec[lc].clear();
vec[rc].clear();
}
int get(int s, int e, int cnt1, int cnt2, int l, int r, int id) {
if(s>=r || l>=e) return 0;
if(s<=l && r<=e) return cnt2 - cnt1;
return get(s, e, cl[id][cnt1], cl[id][cnt2], l, mid, lc)
+ get(s, e, cnt1-cl[id][cnt1], cnt2-cl[id][cnt2], mid, r, rc);
}
public:
inline void add(int x, int y) {
arr.pb({x, y});
}
inline void build() {
sort(all(arr));
n = SZ(arr);
if(!n) return;
vec = vector<vector<int>>(4*n+5);
cl = vector<vector<int>>(4*n+5);
build(0, n, 1);
}
inline int get(int s1, int e1, int s2, int e2) {
if(!n) return 0;
s1 = lower_bound(all(arr), pii(s1, 0))-arr.begin();
e1 = lower_bound(all(arr), pii(e1, 0))-arr.begin();
if(s1>=e1) return 0;
return
get(s1, e1, lower_bound(all(vec[1]), s2)-vec[1].begin(),
lower_bound(all(vec[1]), e2)-vec[1].begin(), 0, n, 1);
}
} v_ds, e_ds, tot_ds;
inline int cnt(vector<pii> &vec, pii s, pii e) {
return lower_bound(all(vec), e)-lower_bound(all(vec), s);
}
inline bool have(vector<pii> &vec, pii x) {
int i = lower_bound(all(vec), x)-vec.begin();
return i<SZ(vec) && vec[i]==x;
}
vector<pii> hor, ver, hor2, ver2;
void init(int R, int C, int sr, int sc, int M, char *S) {
for(int i=0; i<M; i++) {
hor.pb({sr, sc});
if(S[i]=='N') sr--;
else if(S[i]=='W') sc--;
else if(S[i]=='S') sr++;
else if(S[i]=='E') sc++;
}
hor.pb({sr, sc});
sort(all(hor));
hor.resize(unique(all(hor))-hor.begin());
for(auto [x, y] : hor) {
ver.pb({y, x});
bool rgt = have(hor, {x, y+1});
bool dwn = have(hor, {x+1, y});
bool dr = have(hor, {x+1, y+1});
if(rgt) hor2.pb({x, y}), e_ds.add(2*x-1, 2*y);
if(dwn) ver2.pb({y, x}), e_ds.add(2*x, 2*y-1);
if(rgt && dwn && dr) v_ds.add(x, y);
tot_ds.add(x, y);
}
v_ds.build();
e_ds.build();
tot_ds.build();
sort(all(ver));
sort(all(ver2));
}
int colour(int ar, int ac, int br, int bc) {
ll V=1ll*(br-ar+2)*(bc-ac+2);
V -= v_ds.get(ar, br, ac, bc);
V -= cnt(hor2, {ar, ac}, {ar, bc});
V -= cnt(hor2, {br, ac}, {br, bc});
V -= cnt(ver2, {ac, ar}, {ac, br});
V -= cnt(ver2, {bc, ar}, {bc, br});
V -= have(hor, {ar, ac});
V -= have(hor, {ar, bc});
V -= have(hor, {br, ac});
V -= have(hor, {br, bc});
ll E = 1ll*(br-ar+1)*(bc-ac+2) + 1ll*(br-ar+2)*(bc-ac+1);
E -= e_ds.get(2*(ar-1)+1, 2*br, 2*(ac-1)+1, 2*bc);
int edge = 0;
edge += cnt(hor, {ar, ac}, {ar, bc+1});
edge += cnt(hor, {br, ac}, {br, bc+1});
edge += cnt(ver, {ac, ar}, {ac, br+1});
edge += cnt(ver, {bc, ar}, {bc, br+1});
E -= edge;
ll f = 1ll*(br-ar+1)*(bc-ac+1) + 1;
int in = tot_ds.get(ar, br+1, ac, bc+1);
f -= in;
if(in && !edge) f++;
return V + f - E - 1;
}
