#include "rainbow.h"
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
const int MX = 2e5 + 5;
struct segmentTree{
vector<int> st[MX * 2 + 5];
void upd(int ps, int val){
st[ps + MX].push_back(val);
}
void proc(){
for(int i = MX; i < 2 * MX; i ++){
sort(st[i].begin(), st[i].end());
st[i].erase(unique(st[i].begin(), st[i].end()), st[i].end());
}
for(int i = MX - 1; i > 0; i --){
st[i] = vector<int>(st[i * 2].size() + st[i * 2 + 1].size());
merge(st[i * 2].begin(), st[i * 2].end(), st[i * 2 + 1].begin(), st[i * 2 + 1].end(), st[i].begin());
}
}
int que(int lf, int rg, int x, int y){
int ans = 0;
for(lf += MX, rg += MX + 1; lf < rg; lf /= 2, rg /= 2){
if(lf % 2)
ans += upper_bound(st[lf].begin(), st[lf].end(), y) - lower_bound(st[lf].begin(), st[lf].end(), x), lf ++;
if(rg % 2)
rg --, ans += upper_bound(st[rg].begin(), st[rg].end(), y) - lower_bound(st[rg].begin(), st[rg].end(), x);
}
return ans;
}
} vertex, hori, verti, face;
int totalRivers = 0;
void addRiver(int x, int y){
vertex.upd(x, y);
hori.upd(x, y - 1); hori.upd(x, y);
verti.upd(y, x - 1); verti.upd(y, x);
face.upd(x - 1, y - 1); face.upd(x, y - 1); face.upd(x - 1, y); face.upd(x, y);
}
void init(int R, int C, int sr, int sc, int M, char *s) {
addRiver(sr, sc);
for(int i = 0; i < M; i ++){
if(s[i] == 'N') sr --;
if(s[i] == 'S') sr ++;
if(s[i] == 'E') sc ++;
if(s[i] == 'W') sc --;
addRiver(sr, sc);
}
vertex.proc(); hori.proc(); verti.proc(); face.proc();
totalRivers = vertex.que(0, MX - 1, 0, MX - 1);
}
int colour(int ar, int ac, int br, int bc) {
ll H = br - ar + 1, W = bc - ac + 1;
ll V = H * W - vertex.que(ar, br, ac, bc);
ll E = (H - 1) * W + (W - 1) * H - hori.que(ar, br, ac, bc - 1) - verti.que(ac, bc, ar, br - 1);
ll F = (H - 1) * (W - 1) - face.que(ar, br - 1, ac, bc - 1);
if(vertex.que(ar + 1, br - 1, ac + 1, bc - 1) == totalRivers) F ++;
return V - E + F;
}
