#include <bits/stdc++.h>
#include "rainbow.h"
using namespace std;
const int mxn=2e5+5;
///persistent sum segtree
struct segTree{
set<int>pts[mxn];
int roots[mxn];
struct node{
int sum,l,r;
};
node *st;
node def;
int cr = 1;
segTree(int nodes){
st=new node[nodes];
def.sum=0;
def.l=0;
def.r=0;
fill(st,st+nodes,def);
roots[0]=1;
}
void build(){
for(int i = 1;i<mxn;i++){
roots[i]=cpy(roots[i-1]);
for(int y : pts[i]){
update(0,mxn,y,1,roots[i]);
}
}
}
void add(int x, int y){
pts[x].insert(y);
}
int cpy(int ind){
st[++cr]=st[ind];
return cr;
}
void update(int l, int r, int i, int val, int ind){
if(l==r){
st[ind].sum+=val;
return;
}
int mid = (l+r)/2;
if(i<=mid){
st[ind].l=cpy(st[ind].l);
update(l,mid,i,val,st[ind].l);
}
else{
st[ind].r=cpy(st[ind].r);
update(mid+1,r,i,val,st[ind].r);
}
st[ind].sum=st[st[ind].l].sum+st[st[ind].r].sum;
}
int query(int l, int r, int s, int e, int ind){
if(st[ind].sum==0){
return 0;
}
if(e<l||s>r)
return 0;
if(s<=l&&r<=e){
return st[ind].sum;
}
int mid = (l+r)/2;
return query(l,mid,s,e,st[ind].l)+query(mid+1,r,s,e,st[ind].r);
}
};
const int nodes = 1e7;
segTree verts(nodes), rivers(nodes), edges_horizontal(nodes), edges_vertical(nodes);
void add_river(int x, int y){
///add vertices
verts.add(x,y);
verts.add(x+1,y);
verts.add(x,y+1);
verts.add(x+1,y+1);
rivers.add(x,y);
edges_horizontal.add(x,y);
edges_horizontal.add(x+1,y);
edges_vertical.add(x,y);
edges_vertical.add(x,y+1);
}
void init(int R, int C, int sr, int sc, int M, char *S) {
add_river(sr,sc);
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_river(sr,sc);
}
verts.build();
rivers.build();
edges_horizontal.build();
edges_vertical.build();
}
int colour(int ar, int ac, int br, int bc) {
int l = (br-ar+1);
int b = (bc-ac+1);
int R = 2*(l+b+2) + rivers.query(0,mxn,ac,bc,rivers.roots[br]) - rivers.query(0,mxn,ac,bc,rivers.roots[ar-1]);
int V = 4*(l+b+2) + verts.query(0,mxn,ac+1,bc,verts.roots[br]) - verts.query(0,mxn,ac+1,bc,verts.roots[ar]);
int E = edges_horizontal.query(0,mxn,ac,bc,edges_horizontal.roots[br]) - edges_horizontal.query(0,mxn,ac,bc,edges_horizontal.roots[ar]);
E+=edges_vertical.query(0,mxn,ac+1,bc,edges_vertical.roots[br]) - edges_vertical.query(0,mxn,ac+1,bc,edges_vertical.roots[ar-1]);
E+=4*l+4*b+8+8+2*(b-1)+2*(l-1);
int C = (((rivers.query(0,mxn,ac,ac,rivers.roots[br]) - rivers.query(0,mxn,ac,ac,rivers.roots[ar-1]))||(rivers.query(0,mxn,bc,bc,rivers.roots[br]) - rivers.query(0,mxn,bc,bc,rivers.roots[ar-1]))||(rivers.query(0,mxn,ac,bc,rivers.roots[br]) - rivers.query(0,mxn,ac,bc,rivers.roots[br-1]))||(rivers.query(0,mxn,ac,bc,rivers.roots[ar]) - rivers.query(0,mxn,ac,bc,rivers.roots[ar-1])))&&(R-2*(l+b+2))) ? 1 : 2;
return E-V+C-R;
}
