#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, f_ds;
inline bool have(vector<pii> &vec, pii x) {
int i = lower_bound(all(vec), x)-vec.begin();
return i<SZ(vec) && vec[i]==x;
}
int mnx=1e9, mxx=-1e9, mny=1e9, mxy=-1e9;
vector<pii> pnt;
void init(int R, int C, int sr, int sc, int M, char *S) {
for(int i=0; i<M; i++) {
pnt.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++;
}
pnt.pb({sr, sc});
sort(all(pnt));
pnt.resize(unique(all(pnt))-pnt.begin());
for(auto [x, y] : pnt) {
v_ds.add(x, y);
bool h0 = have(pnt, {x-1, y-1});
bool h1 = have(pnt, {x-1, y});
bool h2 = have(pnt, {x-1, y+1});
bool h3 = have(pnt, {x, y-1});
if(!h0 && !h1 && !h3) f_ds.add(x-1, y-1);
if(!h1 && !h2) f_ds.add(x-1, y);
if(!h3) f_ds.add(x, y-1);
f_ds.add(x, y);
if(!h1) e_ds.add(2*(x-1), 2*(y-1)+1);
if(!h3) e_ds.add(2*(x-1)+1, 2*(y-1));
e_ds.add(2*x, 2*y-1);
e_ds.add(2*x-1, 2*y);
mnx = min(mnx, x);
mxx = max(mxx, x);
mny = min(mny, y);
mxy = max(mxy, y);
}
v_ds.build();
e_ds.build();
f_ds.build();
}
int colour(int ar, int ac, int br, int bc) {
ll V=1ll*(br-ar+1)*(bc-ac+1) - v_ds.get(ar, br+1, ac, bc+1);
ll E = 1ll*(br-ar+1)*(bc-ac) + 1ll*(br-ar)*(bc-ac+1) - e_ds.get(2*(ar-1)+1, 2*br, 2*(ac-1)+1, 2*bc);
ll f = 1ll*(br-ar)*(bc-ac) - f_ds.get(ar, br, ac, bc) + 1;
if(ar<mnx && br>mxx && ac<mny && bc>mxy) f++;
return V + f - E - 1;
}
