//#include "rainbow.h"
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
using ll = int; using pii = pair<ll,ll>;
const ll INF = 1e9;
vector<pii> vv; //snake vertices
vector<pii> vev,veh; //snake edges
//vev: (x,y) -> (x+1,y)
//veh: (x,y) -> (x,y+1)
vector<pii> vf; //snake ~internal faces
ll xsmin = INF; ll ysmin = INF; ll xsmax = -1; ll ysmax = -1;
inline ll v2(ll x) {
return __builtin_ctz(x);
}
const ll Nm = 524288; const ll Es = 19;
map<ll,ll> mv[2*Nm];
void prcV(vector<pii> v0) {
sort(v0.begin(),v0.end());
vector<ll> mv0;
for (ll t=0;t<(2*Nm);t++) {
mv[t][-1]=0;
mv0.push_back(0);
}
for (pii p0: v0) {
ll x = p0.first; ll y = p0.second;
ll p = y+Nm;
do {
mv0[p]++;
mv[p][x]=mv0[p];
p=p/2;
} while (p>0);
}
}
ll qryV(ll x, ll y) {
ll ans = 0;
while (y>=0) {
ll vy = v2(y+1);
ll p = (y>>vy)+(1<<(Es-vy));
ans += (*(--mv[p].upper_bound(x))).second;
y -= (1<<vy);
}
return ans;
}
vector<pii> clr(vector<pii> v0) {
sort(v0.begin(),v0.end());
v0.erase(unique(v0.begin(),v0.end()),v0.end());
vector<pii> v1;
for (pii p0: v0) {
if (p0.first>=0 && p0.second>=0) {
v1.push_back(p0);
}
}
return v1;
}
void init(ll R, ll C, ll sr, ll sc, ll M, char* S) {
sr--; sc--;
vv.clear(); vev.clear(); veh.clear(); vf.clear();
ll x = sr; ll y = sc;
vv.push_back({x,y});
for (ll t=0;t<M;t++) {
if (S[t]=='N') {
x--;
}
if (S[t]=='S') {
x++;
}
if (S[t]=='E') {
y++;
}
if (S[t]=='W') {
y--;
}
vv.push_back({x,y});
}
for (pii p0: vv) {
ll x1 = p0.first; ll y1 = p0.second;
vev.push_back({x1,y1});
vev.push_back({x1-1,y1});
veh.push_back({x1,y1});
veh.push_back({x1,y1-1});
vf.push_back({x1,y1});
vf.push_back({x1-1,y1});
vf.push_back({x1,y1-1});
vf.push_back({x1-1,y1-1});
}
vv = clr(vv); //remove duplicates / negatives
vev = clr(vev);
veh = clr(veh);
vf = clr(vf);
for (pii p0: vv) {
xsmin = min(xsmin, p0.first);
ysmin = min(ysmin, p0.second);
xsmax = max(xsmax, p0.first);
ysmax = max(ysmax, p0.second);
}
prcV(vv);
}
int colour(ll ar, ll ac, ll br, ll bc) {
ar--; ac--; br--; bc--;
long long V = (long long)(br-ar+1)*(bc-ac+1);
long long E = (long long)(br-ar)*(bc-ac+1)+(br-ar+1)*(bc-ac);
long long F = (long long)(br-ar)*(bc-ac); //INTERNAL faces
if (ar<xsmin && ac<ysmin && br>xsmax && bc>ysmax) {
F++;
}
//cout << "V,E,F init="<<V<<","<<E<<","<<F<<"\n";
//turn the below into dynamic segtree stuff
// for (pii p0: vv) {
// ll x = p0.first; ll y = p0.second;
// if (x>=ar && x<=br && y>=ac && y<=bc) {
// V--;
// }
// }
V -= (qryV(br,bc)+qryV(ar-1,ac-1)-qryV(br,ac-1)-qryV(ar-1,bc));
for (pii p0: vev) {
ll x = p0.first; ll y = p0.second;
if (x>=ar && x<br && y>=ac && y<=bc) { //x<br strict
E--;
}
}
for (pii p0: veh) {
ll x = p0.first; ll y = p0.second;
if (x>=ar && x<=br && y>=ac && y<bc) { //y<bc strict
E--;
}
}
for (pii p0: vf) {
ll x = p0.first; ll y = p0.second;
if (x>=ar && x<br && y>=ac && y<bc) { //x<br,y<bc strict
F--;
}
}
//cout << "V,E,F final="<<V<<","<<E<<","<<F<<"\n";
return (F+V-E);
}
