#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define speedup cin.tie(0)->sync_with_stdio(0);
#define vc vector
using ll = long long;
vc<vc<int>> g, vis;
vc<array<int, 2>> dr = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
void init(int n, int m, int sx, int sy, int k, char *s) {
vis.assign(n + 1, vc<int> (m + 1));
g.assign(n + 1, vc<int> (m + 1));
for (int i = 0; i < k; i++) {
g[sx][sy] = 1;
if (s[i] == 'N') sx--;
if (s[i] == 'S') sx++;
if (s[i] == 'E') sy++;
if (s[i] == 'W') sy--;
g[sx][sy] = 1;
}
}
inline void dfs (int x, int y, int u, int d, int l, int r) {
vis[x][y] = 1;
for (auto [dx, dy] : dr) {
int nx = x + dx, ny = y + dy;
if (nx < u || nx > d || ny < l || ny > r || vis[nx][ny] + g[nx][ny] > 0) continue;
dfs(nx, ny, u, d, l, r);
}
}
int colour(int u, int l, int d, int r) {
for (int i = u; i <= d; i++)
for (int j = l; j <= r; j++)
vis[i][j] = 0;
int ans = 0;
for (int i = u; i <= d; i++) {
for (int j = l; j <= r; j++) {
if (g[i][j] + vis[i][j] == 0) {
dfs(i, j, u, d, l, r);
ans++;
}
}
}
return ans;
}
