#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5;
int n, m, k;
int sx, sy;
string s;
vector<vector<int>> bad;
int p[N];
int sz[N];
int was[N];
int cur;
int id[N];
int get(int u) {
return (p[u] == u ? u : p[u] = get(p[u]));
}
void unite(int u, int v) {
u = get(u);
v = get(v);
if (u == v)
return;
if (sz[u] > sz[v])
swap(u, v);
p[u] = v;
sz[v] += sz[u];
}
void markBads() {
int x = sx, y = sy;
bad[sx][sy] = true;
for (char c : s) {
if (c == 'N')
x--;
if (c == 'S')
x++;
if (c == 'W')
y--;
if (c == 'E')
y++;
bad[x][y] = true;
}
}
void makeUnions() {
fill(id, id+N, -1);
for (int j = 0; j < m; j++) {
p[j] = j;
sz[j] = 1;
p[m+j] = m+j;
sz[m+j] = 1;
}
for (int j = 0; j < m; j++) {
if (!bad[0][j] && !bad[1][j])
unite(j, m+j);
if (j+1 < m && !bad[0][j] && !bad[0][j+1])
unite(j, j+1);
if (j+1 < m && !bad[1][j] && !bad[1][j+1])
unite(m+j, m+j+1);
}
for (int i : {0, 1})
for (int j = 0; j < m; j++)
if (id[get(i*m+j)] == -1)
id[get(i*m+j)] = cur++;
int uni = -1;
for (int j = 0; j < m; j++) {
if (!bad[0][j])
uni = max(uni, get(j));
if (!bad[1][j])
uni = max(uni, get(m+j));
if (bad[0][j])
id[j] = uni;
if (bad[1][j])
id[m+j] = uni;
}
uni = cur-1;
for (int j = m-1; j >= 0; j--) {
if (!bad[0][j])
uni = min(uni, id[j]);
if (!bad[1][j])
uni = min(uni, id[m+j]);
if (bad[0][j])
id[j] = uni;
if (bad[1][j])
id[m+j] = uni;
}
}
void init(int R, int C, int sr, int sc, int M, char *S) {
n = R;
m = C;
sr--;
sc--;
sx = sr;
sy = sc;
s.clear();
for (int i = 0; i < M; i++)
s += S[i];
bad.resize(n, vector<int>(m));
markBads();
if (n == 2)
makeUnions();
}
int colour(int ar, int ac, int br, int bc) {
ar--;
ac--;
br--;
bc--;
int ans = 0;
if (n == 2) {
ans = id[br*m+bc]-id[ar*m+ac]+1;
} else {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
p[i*m+j] = i*m+j;
sz[i*m+j] = 1;
}
}
for (int i = ar; i <= br; i++) {
for (int j = ac; j <= bc; j++) {
if (j+1 <= bc && !bad[i][j] && !bad[i][j+1])
unite(i*m+j, i*m+j+1);
if (i+1 <= br && !bad[i][j] && !bad[i+1][j])
unite(i*m+j, (i+1)*m+j);
}
}
fill(was, was+n*m, false);
for (int i = ar; i <= br; i++) {
for (int j = ac; j <= bc; j++) {
if (bad[i][j])
continue;
ans += !was[get(i*m+j)];
was[get(i*m+j)] = true;
}
}
}
return ans;
}
