#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
struct node{
int s, e, m;
vector<int> val;
node *l, *r;
node(int S, int E){
s = S, e = E, m = (s+e)/2;
if (s!=e){
l = new node(s, m);
r = new node(m+1, e);
}
}
void up(int ind, int nv){
if (s==e)val.pb(nv);
else{
if (ind<=m)l->up(ind, nv);
else r->up(ind, nv);
}
}
void init(){
if (s!=e)l->init(), r->init(), merge(l->val.begin(), l->val.end(), r->val.begin(), r->val.end(), back_inserter(val));
else{
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
}
}
int query(int a, int x, int b, int y){
if (a>b||x>y)return 0;
if (s==a && e==b){
return upper_bound(val.begin(), val.end(), y)-lower_bound(val.begin(), val.end(), x);
}
if (b<=m)return l->query(a, x, b, y);
else if (a>m)return r->query(a, x, b, y);
return l->query(a, x, m, y)+r->query(m+1, x, b, y);
}
}*black, *hori, *vert, *dot;
void add(int x, int y){
black->up(x, y);
hori->up(x, y);
hori->up(x+1, y);
vert->up(x, y);
vert->up(x, y+1);
dot->up(x, y);
dot->up(x+1, y);
dot->up(x, y+1);
dot->up(x+1, y+1);
}
int ccc=0;
void init(signed r, signed c, signed x, signed y, signed m, char *s){
black = new node(1, r+1);
hori = new node(1, r+1);
vert = new node(1, r+1);
dot = new node(1, r+1);
add(x, y);
for (int i=0; i<m; ++i){
if (s[i]=='N')--x;
else if (s[i]=='S')++x;
else if (s[i]=='W')--y;
else ++y;
add(x, y);
}
black->init(), hori->init(), vert->init(), dot->init();
ccc=black->query(1, 1, r+1, c+1);
}
signed colour(signed a, signed b, signed x, signed y){
int e=2*(y-b+1)+2*(x-a+1)+hori->query(a+1, b, x, y)+vert->query(a, b+1, x, y);
int v=dot->query(a+1, b+1, x, y)+2*(x-a+2)+2*(y-b);
return (black->query(a+1, b+1, x-1, y-1)==ccc?2:1)-v+e-black->query(a, b, x, y);
}
