#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
bool r[N][N];
int cpt[N][N];
int R, C, cid = 0;
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, 1, -1};
struct SegTree {
set<int> t[4 * N];
void build(int node, int start, int end) {
if (start == end) {
for (int j = 1; j <= C; j++) {
if (!r[start][j]) {
t[node].insert(cpt[start][j]);
}
}
} else {
int mid = (start + end) / 2;
build(2 * node, start, mid);
build(2 * node + 1, mid + 1, end);
t[node] = t[2 * node];
t[node].insert(t[2 * node + 1].begin(), t[2 * node + 1].end());
}
}
set<int> query(int node, int start, int end, int L, int R) {
if (R < start || end < L) return {};
if (L <= start && end <= R) return t[node];
int mid = (start + end) / 2;
set<int> left = query(2 * node, start, mid, L, R);
set<int> right = query(2 * node + 1, mid + 1, end, L, R);
left.insert(right.begin(), right.end());
return left;
}
};
SegTree st;
bool in(int r, int c) {
return r >= 1 && r <= R && c >= 1 && c <= C;
}
void bfs(int sr, int sc) {
queue<pair<int, int>> q;
q.push({sr, sc});
cpt[sr][sc] = cid;
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (in(nr, nc) && !r[nr][nc] && cpt[nr][nc] == -1) {
cpt[nr][nc] = cid;
q.push({nr, nc});
}
}
}
}
void init(int r, int c, int sr, int sc, int m, char* s) {
R = r;
C = c;
for (int i = 1; i <= R; ++i) {
for (int j = 1; j <= C; ++j) {
r[i][j] = false;
cpt[i][j] = -1;
}
}
cid = 0;
int x = sr, y = sc;
r[x][y] = true;
for (int i = 0; i < m; ++i) {
if (s[i] == 'N') --x;
else if (s[i] == 'S') ++x;
else if (s[i] == 'E') ++y;
else if (s[i] == 'W') --y;
r[x][y] = true;
}
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
if (!r[i][j] && cpt[i][j] == -1) {
bfs(i, j);
cid++;
}
}
}
st.build(1, 1, R);
}
int colour(int r1, int c1, int r2, int c2) {
set<int> res = st.query(1, 1, R, r1, r2);
return res.size();
}
