#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200002; int totalRivers;
struct segment{
vector<int> tree[2*N+5];
inline void update(int i, int v){ tree[i+N].push_back(v); }
inline void getReady(){
for(int i = N;i < 2*N;i++){
sort(tree[i].begin(),tree[i].end());
tree[i].erase(unique(tree[i].begin(),tree[i].end()),tree[i].end());
}
for(int i = N-1;i > 0;i--){ ///basically merge sort
tree[i] = vector<int>(tree[i<<1].size()+tree[i<<1|1].size());
merge(tree[i<<1].begin(),tree[i<<1].end(), tree[i<<1|1].begin(),tree[i<<1|1].end(),tree[i].begin());
}
}
inline int query(int l, int r, int x, int y){
int ans = 0;
for(l += N, r += (N+1);l < r;l >>= 1, r >>= 1){
if(l&1) ans += upper_bound(tree[l].begin(),tree[l].end(),y) - lower_bound(tree[l].begin(),tree[l].end(),x), l++;
if(r&1) r--, ans += upper_bound(tree[r].begin(),tree[r].end(),y) - lower_bound(tree[r].begin(),tree[r].end(),x);
}
return ans;
}
} vertices, horizontal, vertical, faces;
void addRiver(int r, int c){
vertices.update(r,c);
horizontal.update(r,c-1); horizontal.update(r,c);
vertical.update(c,r-1); vertical.update(c,r);
faces.update(r-1,c-1); faces.update(r,c-1); faces.update(r-1,c); faces.update(r,c);
}
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--; else if(S[i] == 'S') sr++; else if(S[i] == 'E') sc++; else sc--;
addRiver(sr,sc);
}
vertices.getReady(); horizontal.getReady(); vertical.getReady(); faces.getReady();
totalRivers = vertices.query(0,N-1,0,N-1);
}
int colour(int T, int L, int B, int R) {
long long H = B - T + 1, W = R - L + 1;
long long V = H * W - vertices.query(T,B,L,R);
long long E = (H-1)*W + (W-1)*H - horizontal.query(T,B,L,R-1) - vertical.query(L,R,T,B-1);
long long F = (H-1)*(W-1) - faces.query(T,B-1,L,R-1);
if(vertices.query(T+1,B-1,L+1,R-1) == totalRivers) F++;
return V - E + F;
}
