#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN=2e5, mxSTS=1e5*19+1;
struct pst {
vector<int> ta[mxN];
int rt[mxN+1], sts=1, st[mxSTS], lc[mxSTS], rc[mxSTS];
void a(array<int, 2> a) {
ta[a[0]].push_back(a[1]);
}
void bld() {
for(int i=0; i<mxN; ++i) {
rt[i+1]=rt[i];
for(int j : ta[i])
upd(j, rt[i+1]);
}
}
void upd(int l1, int &i, int l2=0, int r2=mxN-1) {
st[sts]=st[i]+1;
lc[sts]=lc[i];
rc[sts]=rc[i];
i=sts++;
if(l2==r2)
return;
int m2=(l2+r2)/2;
if(l1<=m2)
upd(l1, lc[i], l2, m2);
else
upd(l1, rc[i], m2+1, r2);
}
int qry(int l1, int r1, int l2, int r2) {
return l2>r2?0:qry(l2, r2, rt[r1+1], 0, mxN-1)-qry(l2, r2, rt[l1], 0, mxN-1);
}
int qry(int l1, int r1, int i, int l2, int r2) {
if(l1<=l2&&r2<=r1)
return st[i];
int m2=(l2+r2)/2;
return (l1<=m2?qry(l1, r1, lc[i], l2, m2):0)+(m2<r1?qry(l1, r1, rc[i], m2+1, r2):0);
}
} stv, ster, stec, sts;
void init(int r, int c, int sr, int sc, int m, char *s) {
set<array<int, 2>> cs{{--sr, --sc}};
for(int i=0; i<m; ++i) {
if(s[i]=='N')
--sr;
else if(s[i]=='S')
++sr;
else if(s[i]=='E')
++sc;
else
--sc;
cs.insert({sr, sc});
}
for(auto a : cs) {
stv.a(a);
if(cs.find({a[0], a[1]+1})!=cs.end())
ster.a(a);
if(cs.find({a[0]+1, a[1]})!=cs.end())
stec.a(a);
if(cs.find({a[0], a[1]+1})!=cs.end()&&cs.find({a[0]+1, a[1]})!=cs.end()&&cs.find({a[0]+1, a[1]+1})!=cs.end())
sts.a(a);
}
stv.bld();
ster.bld();
stec.bld();
sts.bld();
}
int colour(int ar, int ac, int br, int bc) {
--ar, --ac, --br, --bc;
int e=2*(br-ar+bc-ac+4)+ster.qry(ar, br, ac, bc-1)+stec.qry(ar, br-1, ac, bc)+stv.qry(ar, ar, ac, bc)+stv.qry(br, br, ac, bc)+stv.qry(ar, br, ac, ac)+stv.qry(ar, br, bc, bc);
int v=2*(br-ar+bc-ac+4)+stv.qry(ar, br, ac, bc);
int c=!stv.qry(ar, br, ac, bc)||stv.qry(ar, br, ac, bc)-stv.qry(ar+1, br-1, ac+1, bc-1)?1:2;
int s=stv.qry(ar, ar, ac, ac)+stv.qry(ar, ar, bc, bc)+stv.qry(br, br, ac, ac)+stv.qry(br, br, bc, bc)+ster.qry(ar, ar, ac, bc-1)+ster.qry(br, br, ac, bc-1)+stec.qry(ar, br-1, ac, ac)+stec.qry(ar, br-1, bc, bc)+sts.qry(ar, br-1, ac, bc-1);
return e-v+c-s;
}
