#include <bits/stdc++.h>
#include "rainbow.h"
using namespace std;
const int MAXN = 200005;
int n, m, len, ofs, cnt, xmn, xmx, ymn, ymx;
vector <int> ff[MAXN], vv[MAXN], ex[MAXN], ey[MAXN];
int lef[MAXN * 80], rig[MAXN * 80], t[MAXN * 80];
int ffr[MAXN], vvr[MAXN], exr[MAXN], eyr[MAXN];
void ispis (int x, int d) {
if (x == 0) return;
for (int i=0; i<d; i++) cout << ' ';
cout << x << " " << t[x] << endl;
ispis(lef[x], d + 1);
ispis(rig[x], d + 1);
}
void obradi () {
for (int i=0; i<n; i++) {
sort(ff[i].begin(), ff[i].end());
ff[i].erase(unique(ff[i].begin(), ff[i].end()), ff[i].end());
for (auto j : ff[i]) {
vv[i].push_back(j); vv[i].push_back(j+1);
vv[i+1].push_back(j); vv[i+1].push_back(j+1);
ex[i].push_back(j); ex[i+1].push_back(j);
ey[j].push_back(i); ey[j+1].push_back(i);
}
}
for (int i=0; i<=n; i++) {
sort(vv[i].begin(), vv[i].end());
vv[i].erase(unique(vv[i].begin(), vv[i].end()), vv[i].end());
sort(ex[i].begin(), ex[i].end());
ex[i].erase(unique(ex[i].begin(), ex[i].end()), ex[i].end());
}
for (int i=0; i<=m; i++) {
sort(ey[i].begin(), ey[i].end());
ey[i].erase(unique(ey[i].begin(), ey[i].end()), ey[i].end());
}
}
int build (int len) {
int curr = ++cnt;
if (len == 1) return curr;
lef[curr] = build(len/2);
rig[curr] = build(len/2);
return curr;
}
int update (int x, int pos, int lo, int hi) {
int curr = ++cnt;
if (lo == hi) {
t[curr] = t[x] + 1;
return curr;
}
int mid = (lo + hi) / 2;
if (pos <= mid) {
lef[curr] = update(lef[x], pos, lo, mid);
rig[curr] = rig[x];
} else {
lef[curr] = lef[x];
rig[curr] = update(rig[x], pos, mid+1, hi);
}
t[curr] = t[lef[curr]] + t[rig[curr]];
return curr;
}
int upit (int x, int from, int to, int lo, int hi) {
if (from <= lo && hi <= to) return t[x];
if (to < lo || hi < from) return 0;
return upit(lef[x], from, to, lo, (lo + hi)/2) + upit(rig[x], from, to, (lo + hi)/2+1, hi);
}
void tour_init () {
ofs = 1;
while (ofs < max(m+1, n+1)) ofs *= 2;
ffr[0] = build(ofs); vvr[0] = build(ofs);
exr[0] = build(ofs); eyr[0] = build(ofs);
for (int i=0; i<n; i++) {
if (i > 0) ffr[i] = ffr[i-1];
for (auto j : ff[i]) {
ffr[i] = update(ffr[i], j, 0, ofs-1);
}
}
for (int i=0; i<=n; i++) {
if (i > 0) vvr[i] = vvr[i-1];
for (auto j : vv[i]) {
vvr[i] = update(vvr[i], j, 0, ofs-1);
}
if (i > 0) exr[i] = exr[i-1];
for (auto j : ex[i]) {
exr[i] = update(exr[i], j, 0, ofs-1);
}
}
for (int i=0; i<=m; i++) {
if (i > 0) eyr[i] = eyr[i-1];
for (auto j : ey[i]) {
eyr[i] = update(eyr[i], j, 0, ofs-1);
}
}
}
void init (int R, int C, int sx, int sy, int M, char *S) {
n = R; m = C; len = M;
sx--; sy--;
xmn = xmx = sx;
ymn = ymx = sy;
ff[sx].push_back(sy);
for (int i=0; i<len; i++) {
if (S[i] == 'N') sx--;
if (S[i] == 'E') sy++;
if (S[i] == 'S') sx++;
if (S[i] == 'W') sy--;
xmn = min(xmn, sx); xmx = max(xmx, sx);
ymn = min(ymn, sy); ymx = max(ymx, sy);
ff[sx].push_back(sy);
}
obradi();
tour_init();
}
int colour (int x1, int y1, int x2, int y2) {
x1--; y1--; x2--; y2--;
int f = 0, v = 0, e = 0;
f = upit(ffr[x2], y1, y2, 0, ofs-1) - (x1 == 0 ? 0 : upit(ffr[x1-1], y1, y2, 0, ofs-1));
if (x1 < x2 && y1 < y2) v = upit(vvr[x2], y1+1, y2, 0, ofs-1) - upit(vvr[x1], y1+1, y2, 0, ofs-1);
if (x1 < x2) e += upit(exr[x2], y1, y2, 0, ofs-1) - upit(exr[x1], y1, y2, 0, ofs-1);
if (y1 < y2) e += upit(eyr[y2], x1, x2, 0, ofs-1) - upit(eyr[y1], x1, x2, 0, ofs-1);
return e + 1 - v - f + (x1 < xmn && xmx < x2 && y1 < ymn && ymx < y2);
}
