#include "rainbow.h"
#include <fstream>
#include <iostream>
#include <map>
#include <vector>
#define mp make_pair
using namespace std;
const int nmax=200005;
int d1[]={-1,0,1,0};
int d2[]={0,-1,0,1};
map< pair<int,int>,int > rb,norm;
vector<int> ad[10*nmax];
pair<int,int> v[nmax];
int viz[10*nmax];
int a[nmax][2],sum[2][nmax];
int arb[4*nmax];
int n,nr,mnl=2*nmax,mnc=2*nmax,mxl,mxc;
void add_rainbow(int l,int c)
{
if(!rb[mp(l,c)]) v[++n]={l,c};
rb[mp(l,c)]=1;
mnl=min(mnl,l);
mxl=max(mxl,l);
mnc=min(mnc,c);
mxc=max(mxc,c);
}
void add(int l,int c)
{
int p;
if((!rb[mp(l,c)])&&(!norm[mp(l,c)]))
{
norm[mp(l,c)]=++nr;
for(int dir=0;dir<4;dir++)
{
p=norm[mp(l+d1[dir],c+d2[dir])];
if(p)
ad[p].push_back(nr),ad[nr].push_back(p);
}
}
}
int lim,rr,cc,st,dr,ans;
void build(int nod,int l,int r)
{
if(l==r)
{
if(a[l][0]+a[l][1]) arb[nod]=1;
else arb[nod]=0;
return;
}
int m=(l+r)/2;
build(2*nod,l,m);
build(2*nod+1,m+1,r);
arb[nod]=arb[2*nod]+arb[2*nod+1];
if((a[m][0]&a[m+1][0])+(a[m][1]&a[m+1][1]))
arb[nod]--;
}
void query(int nod,int l,int r)
{
if(st<=l&&r<=dr)
{
ans+=arb[nod];
if(st!=l&&((a[l-1][0]&a[l][0])+(a[l-1][1]&a[l][1])))
ans--;
return;
}
int m=(l+r)/2;
if(st<=m) query(2*nod,l,m);
if(m<dr) query(2*nod+1,m+1,r);
}
int slv(int wh,int l,int r)
{
int ret=(sum[wh][r]-sum[wh][l-1]);
if(a[l][wh]==1&&a[l-1][wh]==1)
ret++;
return ret;
}
void init(int R, int C, int sr, int sc, int M, char *S) {
add_rainbow(sr,sc);
rr=R;cc=C;
lim=max(R,C);
if(rr==2)
{
for(int i=1;i<=cc;i++)
for(int j=0;j<2;j++)
a[i][j]=1;
a[sc][sr-1]=0;
}
for(int i=0;i<M;i++)
{
if(S[i]=='N')
sr--;
if(S[i]=='S')
sr++;
if(S[i]=='W')
sc--;
if(S[i]=='E')
sc++;
add_rainbow(sr,sc);
if(rr==2)
{
a[sc][sr-1]=0;
}
}
if(rr==2)
{
for(int i=0;i<2;i++)
for(int j=1;j<=cc;j++)
{
sum[i][j]=sum[i][j-1];
if(a[j][i]==1&&a[j-1][i]==0)
sum[i][j]++;
}
build(1,1,cc);
}
}
void dfs(int x)
{
viz[x]=1;
for(int i=0;i<ad[x].size();i++)
if(!viz[ad[x][i]])
dfs(ad[x][i]);
}
int colour(int ar, int ac, int br, int bc) {
int cc=0;
nr=0;
if(rr==2)
{
ans=0;st=ac;dr=bc;
if(ar!=br)query(1,1,cc);
else
{
ans=slv(br-1,ac,bc);
}
return ans;
}
for(int i=1;i<=n;i++)
for(int p1=-1;p1<=1;p1++)
for(int p2=-1;p2<=1;p2++)
if(v[i].first+p1>=ar&&v[i].first+p1<=br&&v[i].second+p2>=ac&&v[i].second+p2<=bc)
add(v[i].first+p1,v[i].second+p2);
if(!(ar<mnl&&mxl<br&&ac<mnc&&mxc<bc))
{
for(int i=ar; i<=br; i++)
add(i,ac),add(i,bc);
for(int i=ac; i<=bc; i++)
add(ar,i),add(br,i);
}
for(int i=1;i<=nr;i++)
if(!viz[i])
dfs(i),cc++;
if(lim<=50)
{
norm.clear();
for(int i=1; i<=nr; i++)
ad[i].clear(),viz[i]=0;
}
return cc;
}
