#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
#define cps(x) sort(all(x)), (x).erase(unique(all(x)), end(x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#include "rainbow.h"
int r, c;
map <array <int, 2>, int> used[3];
struct Node {
int n;
vector <int> xv, val, val_cell;
vector <array <int, 2>> pt;
void add(int x, int v) {
xv.pb(x);
pt.pb({x, v});
}
int pos(int x) {
return (int)(lower_bound(all(xv), x) - begin(xv));
}
void build() {
cps(xv);
n = SZ(xv);
val.resize(n), val_cell.resize(n);
for (auto & i : pt) {
int x = pos(i[0]);
if (i[1] == 0) val[x]--;
if (i[1] == 1) val[x]++;
if (i[1] == 2) val_cell[x]++;
}
for (int i = 1; i < n; i++) {
val[i] += val[i - 1];
val_cell[i] += val_cell[i - 1];
}
}
int get(int l, int r) {
l = pos(l), r = pos(r + 1) - 1;
if (l > r) return 0;
if (l == 0) return val[r];
return val[r] - val[l - 1];
}
int get_cell(int l, int r) {
l = pos(l), r = pos(r + 1) - 1;
if (l > r) return 0;
if (l == 0) return val_cell[r];
return val_cell[r] - val_cell[l - 1];
}
};
struct SegTree {
int n;
vector <int> xv;
vector <array <int, 3>> pt;
vector <Node> nd;
int pos(int x) {
return (int)(lower_bound(all(xv), x) - xv.begin());
}
void add(int x, int y, int v) {
for (x += n; x > 0; x >>= 1) nd[x].add(y, v);
}
void build() {
for (auto & i : pt) xv.pb(i[0]);
cps(xv);
n = 1;
while (n < SZ(xv)) n <<= 1;
nd.resize(n << 1);
for (auto & i : pt) {
int x = pos(i[0]);
add(x, i[1], i[2]);
}
for (int i = 1; i < (n << 1); i++) nd[i].build();
}
int get(int l, int r, int l2, int r2) {
l = pos(l), r = pos(r + 1);
if (l > r || l2 > r2) return 0;
int res = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (r & 1) res += nd[--r].get(l2, r2);
if (l & 1) res += nd[l++].get(l2, r2);
}
return res;
}
int get_cell(int l, int r, int l2, int r2) {
l = pos(l), r = pos(r + 1);
if (l > r || l2 > r2) return 0;
int res = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (r & 1) res += nd[--r].get_cell(l2, r2);
if (l & 1) res += nd[l++].get_cell(l2, r2);
}
return res;
}
};
SegTree plane;
void set_pt(int x, int y) {
if (used[0].count({x, y})) return;
used[0][{x, y}] = 1;
plane.pt.pb({x, y, 0});
}
void set_edge(int x, int y) {
if (used[1].count({x, y})) return;
used[1][{x, y}] = 1;
plane.pt.pb({x, y, 1});
}
void set_cell(int x, int y) {
if (used[2].count({x, y})) return;
used[2][{x, y}] = 1;
plane.pt.pb({x, y, 2});
}
void add(int x, int y) {
x *= 2, y *= 2;
set_cell(x - 1, y - 1);
set_pt(x, y), set_pt(x - 2, y), set_pt(x, y - 2), set_pt(x - 2, y - 2);
set_edge(x, y - 1), set_edge(x - 1, y), set_edge(x - 1, y - 2), set_edge(x - 2, y - 1);
}
void init(int R, int C, int sr, int sc, int M, char *S) {
r = R, c = C;
int x = sr, y = sc;
add(x, y);
for (int i = 0; i < M; i++) {
if (S[i] == 'N') x--;
if (S[i] == 'S') x++;
if (S[i] == 'W') y--;
if (S[i] == 'E') y++;
add(x, y);
}
plane.build();
}
int colour(int ar, int ac, int br, int bc) {
ar--, ac--;
ar *= 2, ac *= 2, br *= 2, bc *= 2;
int cells = plane.get_cell(ar, br, ac, bc);
int nb_cells = plane.get_cell(ar + 2, br - 2, ac + 2, bc - 2);
int C = 2;
if (cells > nb_cells || cells == 0) C = 1;
return C + plane.get(ar + 1, br - 1, ac + 1, bc - 1) - cells;
}
