#include <bits/stdc++.h>
#include "rainbow.h"
using namespace std;
typedef pair <int, int> pii;
struct pst{
struct node{
int l, r, v;
node() : l(0), r(0), v(0) {}
};
node T[15151515];
int R[202020], r, t, c;
void init(int w) { c = w; }
void insert(int p, int s, int e, int i, int v)
{
T[p].v += v;
if(s == e) return;
else if(i <= (s + e >> 1)){
T[++t] = T[T[p].l]; T[p].l = t;
insert(T[p].l, s, s + e >> 1, i, v);
}
else{
T[++t] = T[T[p].r]; T[p].r = t;
insert(T[p].r, (s + e >> 1) + 1, e, i, v);
}
}
void insert(int p, int v)
{
T[++t] = T[r]; r = t;
insert(r, 1, c, p, v);
}
void root(int p) { R[p] = r; }
int query(int p, int s, int e, int l, int r)
{
if(!p || r < s || e < l) return 0;
else if(l <= s && e <= r){
return T[p].v;
}
else return query(T[p].l, s, s + e >> 1, l, r)
+ query(T[p].r, (s + e >> 1) + 1, e, l, r);
}
int query(int sr, int sc, int er, int ec)
{
return query(R[er], 1, c, sc, ec)
- query(R[sr - 1], 1, c, sc, ec);
}
};
pst T;
vector <int> R1[202020], R2[202020];
vector <int> C1[202020], C2[202020];
vector <pii> V, E1, E2, F;
int lx, ly, rx, ry;
void push(int x, int y)
{
V.emplace_back(x, y);
E1.emplace_back(x, y);
E1.emplace_back(x + 1, y);
E2.emplace_back(x, y);
E2.emplace_back(x, y + 1);
F.emplace_back(x, y);
F.emplace_back(x, y + 1);
F.emplace_back(x + 1, y);
F.emplace_back(x + 1, y + 1);
}
void compress(vector <pii> &V)
{
sort(V.begin(), V.end());
V.erase(unique(V.begin(), V.end()), V.end());
}
void init(int r, int c, int x, int y, int m, char *S)
{
int i, v, e1, e2, f;
T.init(c + 1);
push(x, y);
lx = rx = x; ly = ry = y;
for(i=0; i<m; i++){
if(S[i] == 'N') x --;
else if(S[i] == 'S') x ++;
else if(S[i] == 'W') y --;
else y ++;
push(x, y);
lx = min(lx, x); rx = max(rx, x);
ly = min(ly, y); ry = max(ry, y);
}
compress(V);
compress(E1);
compress(E2);
compress(F);
v = e1 = e2 = f = 0;
for(i=1; i<=r+1; i++){
for(; v<V.size() && V[v].first == i; v++){
T.insert(V[v].second, -1);
}
for(; e1<E1.size() && E1[e1].first == i; e1++){
T.insert(E1[e1].second, 1);
R1[i].push_back(E1[e1].second);
}
for(; e2<E2.size() && E2[e2].first == i; e2++){
T.insert(E2[e2].second, 1);
C1[E2[e2].second].push_back(i);
}
for(; f<F.size() && F[f].first == i; f++){
T.insert(F[f].second, -1);
R2[i].push_back(F[f].second);
C2[F[f].second].push_back(i);
}
T.root(i);
}
}
int colour(int sr, int sc, int er, int ec)
{
int ret = 1 + T.query(sr, sc, er, ec);
ret -= lower_bound(R1[sr].begin(), R1[sr].end(), ec + 1)
- lower_bound(R1[sr].begin(), R1[sr].end(), sc);
ret -= lower_bound(C1[sc].begin(), C1[sc].end(), er + 1)
- lower_bound(C1[sc].begin(), C1[sc].end(), sr);
ret += lower_bound(R2[sr].begin(), R2[sr].end(), ec + 1)
- lower_bound(R2[sr].begin(), R2[sr].end(), sc + 1);
ret += lower_bound(C2[sc].begin(), C2[sc].end(), er + 1)
- lower_bound(C2[sc].begin(), C2[sc].end(), sr);
ret += (sr < lx && rx < er && sc < ly && ry < ec);
return ret;
}
