#include "rainbow.h"
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <set>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
class PersistentSegtree {
public:
int st[20000000], lc[20000000], rc[20000000], cnt = 1;
int heads[200005];
void seg_inc(int n, int pn, int lo, int hi, int i, int v) {
if (lo + 1 == hi) {
st[n] = st[pn] + v;
return;
}
lc[n] = lc[pn], rc[n] = rc[pn];
int mid = (lo + hi) / 2;
if (mid > i) {
lc[n] = cnt++;
seg_inc(lc[n], lc[pn], lo, mid, i, v);
} else {
rc[n] = cnt++;
seg_inc(rc[n], rc[pn], mid, hi, i, v);
}
st[n] = st[lc[n]] + st[rc[n]];
}
int seg_sum(int n, int pn, int lo, int hi, int l, int r) {
if (lo >= r || hi <= l) return 0;
if (lo >= l && hi <= r) {
return st[n] - st[pn];
}
int mid = (lo + hi) / 2;
return seg_sum(lc[n], lc[pn], lo, mid, l, r) + seg_sum(rc[n], rc[pn], mid, hi, l, r);
}
} st[4];
vector<int> rec[4][200005];
set<pii> water, vedges, hedges, verts;
void init(int R, int C, int sr, int sc, int M, char *S) {
water.insert({ sr, sc });
for (int i = 0; i < M; i++) {
if (S[i] == 'N') {
sr -= 1;
} else if (S[i] == 'S') {
sr += 1;
} else if (S[i] == 'E') {
sc += 1;
} else {
sc -= 1;
}
water.insert({ sr, sc });
}
for (pii p : water) {
verts.insert(p);
verts.insert({ p.fi + 1, p.se });
verts.insert({ p.fi, p.se + 1 });
verts.insert({ p.fi + 1, p.se + 1 });
vedges.insert(p);
vedges.insert({ p.fi, p.se + 1 });
hedges.insert(p);
hedges.insert({ p.fi + 1, p.se });
rec[0][p.fi].push_back(p.se);
}
for (pii p : verts) rec[1][p.fi].push_back(p.se);
for (pii p : hedges) rec[2][p.fi].push_back(p.se);
for (pii p : vedges) rec[3][p.fi].push_back(p.se);
for (int j = 0; j < 4; j++) {
for (int i = 1; i <= R; i++) {
int node = st[j].heads[i-1];
for (int x : rec[j][i]) {
int nn = st[j].cnt++;
st[j].seg_inc(nn, node, 1, 200005, x, 1);
node = nn;
}
st[j].heads[i] = node;
}
}
}
int colour(int ar, int ac, int br, int bc) {
int a = st[3].seg_sum(st[3].heads[br], st[3].heads[ar-1], 1, 200005, ac + 1, bc + 1);
int b = st[2].seg_sum(st[2].heads[br], st[2].heads[ar], 1, 200005, ac, bc + 1);
int c = st[1].seg_sum(st[1].heads[br], st[1].heads[ar], 1, 200005, ac + 1, bc + 1);
int d = st[0].seg_sum(st[0].heads[br], st[0].heads[ar-1], 1, 200005, ac, bc + 1);
//printf("Vertical edges: %d\nHorizontal edges: %d\nVertices: %d\nWater: %d\n", a, b, c, d);
if (c == verts.size()) return 2 + a + b - c - d;
return 1 + a + b - c - d;
}
