// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>
#include "rainbow.h"
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int MAXN = (int)2e5 + 5;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const char dc[] = {'E', 'S', 'W', 'N'};
template<int N> struct BIT {
vector<pii> T[N + 5];
void update(int x, int y) {
if (x < 1 || y < 1) {
return;
}
int stx = x;
for (; x <= N; x |= (x + 1)) {
T[x].pb(mp(y, stx));
}
}
void build() {
for (int i = 1; i <= N; ++i) {
sort(all(T[i]));
T[i].resize(unique(all(T[i])) - T[i].begin());
}
}
ll prectS(int x, int ly, int ry) {
ll ret = 0;
for (; x > 0; --x) {
ret += lower_bound(all(T[x]), mp(ry + 1, 0)) - lower_bound(all(T[x]), mp(ly, 0));
x &= (x + 1);
}
return ret;
}
ll rectS(int ax, int bx, int ay, int by) {
if (ax > bx || ay > by) {
return 0;
}
return prectS(bx, ay, by) - prectS(ax - 1, ay, by);
}
};
int mnx, mxx, mny, mxy;
BIT<200000> H[4];
pii arr[MAXN];
int n, m, k;
void init(int R, int C, int stx, int sty, int M, char *S) {
n = R;
m = C;
k = M;
arr[0] = mp(stx, sty);
for (int i = 0; i < k; ++i) {
int dir = find(dc, dc + 4, S[i]) - dc;
stx += dx[dir];
sty += dy[dir];
arr[i + 1] = mp(stx, sty);
}
mnx = mxx = arr[0].fi;
mny = mxy = arr[0].se;
for (int i = 0; i <= k; ++i) {
int x, y;
tie(x, y) = arr[i];
mnx = min(mnx, x);
mxx = max(mxx, x);
mny = min(mny, y);
mxy = max(mxy, y);
H[0].update(x, y);
H[1].update(x, y);
H[1].update(x - 1, y);
H[2].update(x, y);
H[2].update(x, y - 1);
H[3].update(x, y);
H[3].update(x - 1, y);
H[3].update(x, y - 1);
H[3].update(x - 1, y - 1);
}
H[0].build();
H[1].build();
H[2].build();
H[3].build();
}
int colour(int ax, int ay, int bx, int by) {
ll ans = 1;
if (ax < mnx && mxx < bx && ay < mny && mxy < by) {
++ans;
}
ans += H[1].rectS(ax, bx - 1, ay, by);
ans += H[2].rectS(ax, bx, ay, by - 1);
ans -= H[3].rectS(ax, bx - 1, ay, by - 1);
ans -= H[0].rectS(ax, bx, ay, by);
return ans;
}
