#include<bits/stdc++.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=2e5+3;
const int mod=1e9+7;
const int INF=1e9+7;
int R,C,m,q;
string s;
struct node
{
int val1,val2,val3;
node *l,*r;
node(): val1(0),val2(0),val3(0),l(NULL),r(NULL){};
}*rootc[maxn],*rootr[maxn];
node* cons(node* kk,int cl,int cr)
{
if(cl==cr) return new node();
int mid=(cl+cr)/2;
kk=new node();
kk->l=cons(kk->l,cl,mid);
kk->r=cons(kk->r,mid+1,cr);
return kk;
}
node* update(node* kk,int cl,int cr,int pos,int val,int type)
{
node* kkk=new node();
kkk->val1=kk->val1;
kkk->val2=kk->val2;
kkk->val3=kk->val3;
kkk->l=kk->l;
kkk->r=kk->r;
if(cl==cr)
{
if(type==1) kkk->val1+=val;
else if(type==2) kkk->val2+=val;
else kkk->val3+=val;
return kkk;
}
int mid=(cl+cr)/2;
if(pos<=mid) kkk->l=update(kk->l,cl,mid,pos,val,type);
else kkk->r=update(kk->r,mid+1,cr,pos,val,type);
kkk->val1=kkk->l->val1+kkk->r->val1;
kkk->val2=kkk->l->val2+kkk->r->val2;
kkk->val3=kkk->l->val3+kkk->r->val3;
return kkk;
}
int get(node* kk,int cl,int cr,int l,int r,int type)
{
if(cl>r||cr<l) return 0;
if(cl>=l&&cr<=r)
{
if(type==1) return kk->val1;
else if(type==2) return kk->val2;
else return kk->val3;
}
int mid=(cl+cr)/2;
return get(kk->l,cl,mid,l,r,type)+get(kk->r,mid+1,cr,l,r,type);
}
set<pii> path;
set<int> row[maxn],col[maxn],blc[maxn],blr[maxn];
void init(int32_t _R,int32_t _C,int32_t SR,int32_t SC,int32_t M,char* t)
{
R=_R;
C=_C;
m=M;
path.insert({SR,SC});
for(int i=0;i<M;i++)
{
char x=t[i];
if(x=='N') SR--;
if(x=='S') SR++;
if(x=='E') SC++;
if(x=='W') SC--;
path.insert({SR,SC});
}
for( pii x:path)
{
row[x.fi].insert(x.sc);
row[x.fi-1].insert(x.sc);
col[x.sc].insert(x.fi);
col[x.sc-1].insert(x.fi);
blr[x.fi].insert(x.sc);
blr[x.fi-1].insert(x.sc);
blr[x.fi].insert(x.sc-1);
blr[x.fi-1].insert(x.sc-1);
blc[x.fi].insert(x.sc);
}
rootr[0]=cons(rootr[0],0,C);
for(int i=1;i<=R;i++)
{
rootr[i]=rootr[i-1];
for(int x:row[i])
{
rootr[i]=update(rootr[i],0,C,x,1,1);
}
for(int x:blc[i])
{
rootr[i]=update(rootr[i],0,C,x,1,2);
}
for(int x:blr[i])
{
rootr[i]=update(rootr[i],0,C,x,1,3);
}
}
rootc[0]=cons(rootc[0],0,R);
for(int i=1;i<=C;i++)
{
rootc[i]=rootc[i-1];
for(int x:col[i])
{
rootc[i]=update(rootc[i],0,R,x,1,1);
}
}
}
int colour(int32_t ar,int32_t ac,int32_t br,int32_t bc)
{
int border=2*(br-ar+bc-ac+2);
int rr=get(rootr[br-1],0,C,ac,bc,1)-get(rootr[ar-1],0,C,ac,bc,1);
int cc=get(rootc[bc-1],0,R,ar,br,1)-get(rootc[ac-1],0,R,ar,br,1);
int block=get(rootr[br],0,C,ac,bc,2)-get(rootr[ar-1],0,C,ac,bc,2);
int vert=get(rootr[br-1],0,C,ac,bc-1,3)-get(rootr[ar-1],0,C,ac,bc-1,3);
return rr+cc+2-block-vert-1;
return 0;
}
//signed main()
//{
// if (fopen(taskname".INP","r"))
// {
// freopen(taskname".INP","r",stdin);
// freopen(taskname".OUT","w",stdout);
// }
// Faster
// init(6, 4, 3, 3, 9,"NWESSWEWS");
// cout<<colour(2,3,2,3)<<"\n";
// cout<<colour(3,2,4,4)<<"\n";
// cout<<colour(5,3,6,4)<<"\n";
// cout<<colour(1,2,5,3)<<"\n";
//
//}
