#include "rainbow.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 13;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int dir[256];
int bx1 = INT32_MAX, bx2 = INT32_MIN, by1 = INT32_MAX, by2 = INT32_MIN;
struct DS{
unordered_set<ll> S;
vector<int> bits[N];
string name;
DS(string _n) : name(_n){}
void add(int x, int y){
x++; y++;
if(S.count(x * N + y))
return;
S.insert(x * N + y);
for(int i = x; i < N; i += i & -i){
bits[i].push_back(y);
}
}
void load(){
for(int i = 0; i < N; i++){
sort(bits[i].begin(), bits[i].end());
}
}
int qry(int x, int y){
x++; y++;
int ret = 0;
for(int i = x; i; i -= i & -i){
ret += upper_bound(bits[i].begin(), bits[i].end(), y) - bits[i].begin();
}
return ret;
}
int qry(int x1, int x2, int y1, int y2){
return qry(x2, y2) + qry(x1 - 1, y1 - 1) - qry(x2, y1 - 1) - qry(x1 - 1, y2);
}
} V("V"), E1("E1"), E2("E2"), SQ("SQ");
void upd(int x, int y){
bx1 = min(bx1, x);
bx2 = max(bx2, x);
by1 = min(by1, y);
by2 = max(by2, y);
V.add(x, y);
E1.add(x, y - 1);
E1.add(x, y);
E2.add(x - 1, y);
E2.add(x, y);
SQ.add(x - 1, y - 1);
SQ.add(x - 1, y);
SQ.add(x, y - 1);
SQ.add(x, y);
}
void init(int R, int C, int sr, int sc, int M, char *S) {
dir['E'] = 0;
dir['W'] = 1;
dir['S'] = 2;
dir['N'] = 3;
upd(sr, sc);
for(int i = 0; i < M; i++){
sr += dx[dir[S[i]]];
sc += dy[dir[S[i]]];
upd(sr, sc);
}
V.load();
E1.load();
E2.load();
SQ.load();
}
int colour(int ar, int ac, int br, int bc) {
int x1 = ar, x2 = br, y1 = ac, y2 = bc;
int v = (x2 - x1 + 1) * (y2 - y1 + 1) - V.qry(x1, x2, y1, y2);
int e1 = (x2 - x1 + 1) * (y2 - y1) - E1.qry(x1, x2, y1, y2 - 1);
int e2 = (x2 - x1) * (y2 - y1 + 1) - E2.qry(x1, x2 - 1, y1, y2);
int sq = (x2 - x1) * (y2 - y1) - SQ.qry(x1, x2 - 1, y1, y2 - 1);
return v - e1 - e2 + sq + (x1 < bx1 && bx2 < x2 && y1 < by1 && by2 < y2);
}
