#include "rainbow.h"
#include<bits/stdc++.h>
const int inf=1e9;
using namespace std;
vector<vector<int>>dx={{0},{0,1},{0},{0,1}};
vector<vector<int>>dy={{0},{0,1},{0,1},{0}};
struct bit
{
vector<pair<int,int>>add;
vector<int>v[200005];
void init()
{
sort(add.begin(),add.end());
add.resize(unique(add.begin(),add.end())-add.begin());
int i;
for(auto it:add)
for(i=it.first;i<=200000;i=i+(i&-i))
v[i].push_back(it.second);
for(i=1;i<=200000;i++)
sort(v[i].begin(),v[i].end());
}
int query(int x,int st,int dr)
{
int ans=0;
for(;x>=1;x=x-(x&-x)){
auto it1=lower_bound(v[x].begin(),v[x].end(),st);
auto it2=upper_bound(v[x].begin(),v[x].end(),dr);
ans=ans+it2-it1;
}
return ans;
}
int query2(int st,int dr,int l,int r)
{
if (st>dr || l>r)
return 0;
return query(dr,l,r)-query(st-1,l,r);
}
}aib[4];
int minr=inf,minc=inf,maxr=-inf,maxc=-inf;
void add(pair<int,int>aux)
{
minr=min(minr,aux.first);
maxr=max(maxr,aux.first);
minc=min(minc,aux.second);
maxc=max(maxc,aux.second);
int i;
for(i=0;i<4;i++)
for(auto x:dx[i])
for(auto y:dy[i])
aib[i].add.push_back(make_pair(aux.first+x,aux.second+y));
}
void init(int r,int c,int sr,int sc,int m,char *s)
{
pair<int,int>poz;
poz=make_pair(sr,sc);
add(poz);
int i;
for(i=0;i<m;i++){
if (s[i]=='N')
poz.first--;
if (s[i]=='E')
poz.second++;
if (s[i]=='S')
poz.first++;
if (s[i]=='W')
poz.second--;
add(poz);
}
for(i=0;i<4;i++)
aib[i].init();
}
int colour(int st,int l,int dr,int r)
{
int nr1=aib[1].query2(st+1,dr,l+1,r),nr2=aib[0].query2(st,dr,l,r),nr3=aib[2].query2(st,dr,l+1,r)+aib[3].query2(st+1,dr,l,r);
int ans=nr3-nr1-nr2+1;
if (st<minr && maxr<dr && l<minc && maxc<r)
ans++;
return ans;
}
