#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
#include "rainbow.h"
struct seg {
vector<int> *t;
void init(int sz) { t = new vector<int>[4*sz]; }
void add(int p, int x, int i, int b, int e) {
if (e-b == 1) {
t[i].push_back(x);
return;
}
if (p < (b+e)/2)
add(p, x, 2*i+1, b, (b+e)/2);
else
add(p, x, 2*i+2, (b+e)/2, e);
}
void build(int i, int b, int e) {
if (e-b == 1) {
sort(t[i].begin(), t[i].end());
auto it = unique(t[i].begin(), t[i].end());
t[i].resize(it - t[i].begin());
return;
}
build(2*i+1, b, (b+e)/2);
build(2*i+2, (b+e)/2, e);
merge(t[2*i+1].begin(), t[2*i+1].end(),
t[2*i+2].begin(), t[2*i+2].end(),
back_inserter(t[i]));
}
int get(int l1, int r1, int l2, int r2, int i, int b, int e) {
if (l1 <= b && e <= r1) {
return lower_bound(t[i].begin(), t[i].end(), r2)
- lower_bound(t[i].begin(), t[i].end(), l2);
}
if (r1 <= b || e <= l1)
return 0;
return get(l1, r1, l2, r2, 2*i+1, b, (b+e)/2)
+ get(l1, r1, l2, r2, 2*i+2, (b+e)/2, e);
}
} seg_edge_h, seg_edge_v, seg_node, seg_river;
int n, m;
int rmn = INT_MAX, rmx = 0;
int cmn = INT_MAX, cmx = 0;
void add_river(int i, int j)
{
seg_edge_h.add(i, j, 0, 0, n+1);
seg_edge_h.add(i+1, j, 0, 0, n+1);
seg_edge_v.add(i, j, 0, 0, n+1);
seg_edge_v.add(i, j+1, 0, 0, n+1);
seg_node.add(i, j, 0, 0, n+1);
seg_node.add(i, j+1, 0, 0, n+1);
seg_node.add(i+1, j, 0, 0, n+1);
seg_node.add(i+1, j+1, 0, 0, n+1);
seg_river.add(i, j, 0, 0, n);
rmn = min(rmn, i);
rmx = max(rmx, i);
cmn = min(cmn, j);
cmx = max(cmx, j);
}
void init(int R, int C, int sr, int sc, int M, char *S)
{
n = R; m = C;
seg_edge_h.init(n+1);
seg_edge_v.init(n+1);
seg_node.init(n+1);
seg_river.init(n);
int x = sr - 1, y = sc - 1;
add_river(x, y);
Loop (i,0,M) {
char c = S[i];
x -= c == 'N';
x += c == 'S';
y -= c == 'W';
y += c == 'E';
add_river(x, y);
}
seg_edge_h.build(0, 0, n+1);
seg_edge_v.build(0, 0, n+1);
seg_node.build(0, 0, n+1);
seg_river.build(0, 0, n);
}
int colour(int ar, int ac, int br, int bc)
{
--ar; --ac;
int edges = 0, nodes = 0, rivers = 0, comps = 0;
edges += seg_edge_h.get(ar+1, br, ac, bc, 0, 0, n+1);
edges += seg_edge_v.get(ar, br, ac+1, bc, 0, 0, n+1);
edges += 2*(br - ar) + 2*(bc - ac);
nodes += seg_node.get(ar+1, br, ac+1, bc, 0, 0, n+1);
nodes += 2*(br - ar) + 2*(bc - ac);
rivers += seg_river.get(ar, br, ac, bc, 0, 0, n);
comps = 1 + (ar < rmn && rmx+1 < br && ac < cmn && cmx+1 < bc);
int ans = edges - nodes + comps - rivers;
return ans;
}
