#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int S=(1<<18);
class PST {
public:
PST() {tree.push_back({0, 0, 0}), tree.push_back({0, 0, 0}), cnt=1, root.push_back(1);}
void init(vector<pair<int, int>> v) {
for(auto i:v) {
x.push_back(i.first);
root.push_back(update(root.back(), 1, S, i.second));
}
}
int query(int sx, int sy, int ex, int ey) {
auto p=lower_bound(x.begin(), x.end(), sx), q=upper_bound(x.begin(), x.end(), ex);
return max(0, query(root[q-x.begin()], 1, S, sy, ey)-query(root[p-x.begin()], 1, S, sy, ey));
}
private:
int cnt;
struct Node {
int x, l, r;
};
vector<Node> tree;
vector<int> x;
vector<int> root;
int update(int prev, int s, int e, int k) {
int node=++cnt;
tree.push_back({0, 0, 0});
tree[node].x=tree[prev].x, tree[node].l=tree[prev].l, tree[node].r=tree[prev].r;
tree[node].x++;
if(s==e) return node;
int m=(s+e)/2;
if(k<=m) tree[node].l=update(tree[prev].l, s, m, k);
else tree[node].r=update(tree[prev].r, m+1, e, k);
return node;
}
int query(int node, int s, int e, int l, int r) {
if(!node || s>e || l>r) return 0;
if(l<=s && e<=r) return tree[node].x;
int m=(s+e)/2;
return query(tree[node].l, s, m, l, r)+query(tree[node].r, m+1, e, l, r);
}
}V, E1, E2, F;
void init(int R, int C, int sr, int sc, int M, char *S) {
vector<pair<int, int>> v, e1, e2, f;
v.push_back({sr, sc}), v.push_back({sr+1, sc}), v.push_back({sr, sc+1}), v.push_back({sr+1, sc+1});
e1.push_back({sr, sc}), e1.push_back({sr, sc+1}), e2.push_back({sr, sc}), e2.push_back({sr+1, sc}), f.push_back({sr, sc});
for(int i=0; i<M; i++) {
if(S[i]=='E') sc++;
else if(S[i]=='W') sc--;
else if(S[i]=='N') sr--;
else sr++;
v.push_back({sr, sc}), v.push_back({sr+1, sc}), v.push_back({sr, sc+1}), v.push_back({sr+1, sc+1});
e1.push_back({sr, sc}), e1.push_back({sr, sc+1}), e2.push_back({sr, sc}), e2.push_back({sr+1, sc}), f.push_back({sr, sc});
}
sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end());
sort(e1.begin(), e1.end()), e1.erase(unique(e1.begin(), e1.end()), e1.end());
sort(e2.begin(), e2.end()), e2.erase(unique(e2.begin(), e2.end()), e2.end());
sort(f.begin(), f.end()), f.erase(unique(f.begin(), f.end()), f.end());
V.init(v), E1.init(e1), E2.init(e2), F.init(f);
}
int colour(int ar, int ac, int br, int bc) {
int v=V.query(ar+1, ac+1, br, bc)+2*(br-ar+1+bc-ac+1);
int e=E1.query(ar, ac+1, br, bc)+E2.query(ar+1, ac, br, bc)+2*(br-ar+1+bc-ac+1);
int f=F.query(ar, ac, br, bc);
int c=1+((F.query(ar, ac, ar, bc)+F.query(ar, ac, br, ac)+F.query(br, ac, br, bc)+F.query(ar, bc, br, bc)==0) && (F.query(ar, ac, br, bc)>0));
return -v+e-f+c;
}
