#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
struct pt{ int x,y;pt(){}pt(int a, int b):x(a),y(b){}};
pt operator - (pt a, pt b){ return pt(a.x-b.x,a.y-b.y);}
bool operator < (pt a, pt b){ return mp(a.x,a.y)<mp(b.x,b.y);}
bool operator == (pt a, pt b){ return mp(a.x,a.y)==mp(b.x,b.y);}
vector<pt> v[4];
void Add(pt p)
{
v[0].pb(p);
v[1].pb(p);v[1].pb(p-pt(1,0));
v[2].pb(p);v[2].pb(p-pt(0,1));
v[3].pb(p);v[3].pb(p-pt(1,0));v[3].pb(p-pt(0,1));v[3].pb(p-pt(1,1));
}
const int N=400050;
void ckmn(int &a, int b){ a=min(a,b);}
void ckmx(int &a, int b){ a=max(a,b);}
int d;
bool comp(pt a, pt b){ return d==0?a<b:mp(a.y,a.x)<mp(b.y,b.x);}
struct KDTree
{
int ls[N],rs[N],tsz,root,sum[N];
pt p[N],l[N],r[N];
KDTree(){}
void upd_mn(int c, pt f){ ckmn(l[c].x,f.x);ckmn(l[c].y,f.y);}
void upd_mx(int c, pt f){ ckmx(r[c].x,f.x);ckmx(r[c].y,f.y);}
void Build(int &c, int d, vector<pt> v)
{
if(v.empty()) return;
c=++tsz;
::d=d;
int mid=(v.size()-1)/2;
nth_element(v.begin(),v.begin()+mid,v.end());
p[c]=l[c]=r[c]=v[mid];sum[c]=1;
vector<pt> u(v.begin()+mid+1,v.end());
v.resize(mid);
Build(ls[c],d^1,v);
Build(rs[c],d^1,u);
if(ls[c]) upd_mn(c,l[ls[c]]),upd_mx(c,r[ls[c]]),sum[c]+=sum[ls[c]];
if(rs[c]) upd_mn(c,l[rs[c]]),upd_mx(c,r[rs[c]]),sum[c]+=sum[rs[c]];
}
void Build(vector<pt> v){ Build(root,0,v);}
int Get(int c, int d, pt qs, pt qe)
{
if(!c) return 0;
if(qs.x<=l[c].x && qs.y<=l[c].y && qe.x>=r[c].x && qe.y>=r[c].y) return sum[c];
if(qe.x<l[c].x || qe.y<l[c].y || qs.x>r[c].x || qs.y>r[c].y) return 0;
int ans=0;
if(qs.x<=p[c].x && qs.y<=p[c].y && qe.x>=p[c].x && qe.y>=p[c].y) ans++;
ans+=Get(ls[c],d^1,qs,qe);
ans+=Get(rs[c],d^1,qs,qe);
return ans;
}
ll Get(int x1, int y1, int x2, int y2)
{
if(x2<x1 || y2<y1) return 0;
pt L(x1,y1),R(x2,y2);
return (ll)(x2-x1+1)*(y2-y1+1)-Get(root,0,L,R);
}
} KDT[4];
void Build()
{
for(int i=0;i<4;i++)
{
sort(v[i].begin(),v[i].end());
v[i].resize(unique(v[i].begin(),v[i].end())-v[i].begin());
KDT[i].Build(v[i]);
}
}
pt mn,mx;
void init(int R, int C, int sr, int sc, int M, char *S)
{
pt pos(sr,sc);
Add(pos);
for(int i=0;i<M;i++)
{
if(S[i]=='N') pos.x--;
if(S[i]=='S') pos.x++;
if(S[i]=='W') pos.y--;
if(S[i]=='E') pos.y++;
Add(pos);
}
Build();
mn=KDT[0].l[KDT[0].root];
mx=KDT[0].r[KDT[0].root];
}
int colour(int x1, int y1, int x2, int y2)
{
ll ans=KDT[0].Get(x1,y1,x2,y2)-KDT[1].Get(x1,y1,x2-1,y2)-KDT[2].Get(x1,y1,x2,y2-1)+KDT[3].Get(x1,y1,x2-1,y2-1);
if(x1<mn.x && y1<mn.y && x2>mx.x && y2>mx.y) ans++;
return ans;
}
