#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
vector<int> pos[4][maxn];
vector<int> FW[4][maxn];
vector<pair<int, int>> E[4];
int r, c;
void fadd(int x, int y, int id){
for(x; x <= r; x += x&(-x))pos[id][x].push_back(y);
}
void add(int x, int y, int id){
for(x; x <= r; x += x&(-x)){
for(int idx = lower_bound(pos[id][x].begin(), pos[id][x].end(), y) - pos[id][x].begin(); idx < FW[id][x].size(); idx += idx&(-idx)){
FW[id][x][idx]++;
}
}
}
int query(int x, int y, int id){
int re = 0;
for(x; x > 0; x -= x&(-x)){
for(int idx = upper_bound(pos[id][x].begin(), pos[id][x].end(), y) - pos[id][x].begin() - 1; idx > 0; idx -= idx&(-idx)){
re += FW[id][x][idx];
}
}
return re;
}
int query_rect(int x1, int y1, int x2, int y2, int id){
if(x1 > x2 || y1 > y2)return 0;
return query(x2, y2, id) - query(x1-1, y2, id) - query(x2, y1-1, id) + query(x1-1, y1-1, id);
}
void add_square(int sr, int sc){
// cout << sr << " " << sc << endl;
E[0].push_back({sr, sc});
E[0].push_back({sr+1, sc});
E[1].push_back({sr, sc});
E[1].push_back({sr, sc+1});
E[2].push_back({sr, sc});
E[3].push_back({sr, sc});
E[3].push_back({sr, sc+1});
E[3].push_back({sr+1, sc+1});
E[3].push_back({sr+1, sc});
}
void init(int R, int C, int sr, int sc, int M, char *S) {
r = R;
c = C;
add_square(sr, sc);
for(int i = 0; i < M; i++){
if(S[i] == 'N')sr--;
else if(S[i] == 'W')sc--;
else if(S[i] == 'S')sr++;
else sc++;
add_square(sr, sc);
}
for(int id = 0; id < 4; id++){
sort(E[id].begin(), E[id].end());
E[id].erase(unique(E[id].begin(), E[id].end()), E[id].end());
for(auto v: E[id])fadd(v.first, v.second, id);
for(int i = 1; i <= r; i++){
pos[id][i].push_back(-1);
sort(pos[id][i].begin(), pos[id][i].end());
pos[id][i].erase(unique(pos[id][i].begin(), pos[id][i].end()), pos[id][i].end());
FW[id][i].assign(pos[id][i].size(), 0);
}
for(auto v: E[id])add(v.first, v.second, id);
}
}
// V - E + F - C = 1 => F = 1 + C + E - V
//
int colour(int ar, int ac, int br, int bc) {
int F = query_rect(ar, ac, br, bc, 2);
if(F == 0)return 1;
int V = (br - ar + 1)*2 + (bc - ac + 1)*2 + query_rect(ar+1, ac+1, br, bc, 3);
int E = (br - ar + 1)*2 + (bc - ac + 1)*2 + query_rect(ar+1, ac, br, bc, 0) + query_rect(ar, ac+1, br, bc, 1);
int C = 1 + (query_rect(ar+1, ac+1, br-1, bc-1, 2) == F);
F++;
return 1 + C + E - V - F;
}
