#include <bits/stdc++.h>
#include "rainbow.h"
// #include "grader.cpp"
using namespace std;
int n, m;
vector<vector<bool>> rv;
vector<int> dX = {-1, 0, 1, 0}, dY = {0, 1, 0, -1};
void init(int R, int C, int sr, int sc, int M, char *S) {
n = R; m = C;
sr--; sc--;
rv.assign(n, vector<bool>(m));
rv[sr][sc] = true;
for (int i = 0; i < M; i++) {
if (S[i] == 'N') sr--;
else if (S[i] == 'S') sr++;
else if (S[i] == 'W') sc--;
else sc++;
rv[sr][sc] = true;
}
}
int colour(int ar, int ac, int br, int bc) {
ar--; ac--; br--; bc--;
int cnt = 0;
vector<vector<bool>> vis(n, vector<bool>(m));
for (int i = ar; i <= br; i++) {
for (int j = ac; j <= bc; j++) {
if (rv[i][j] || vis[i][j]) continue;
cnt++;
queue<pair<int, int>> q;
q.push({i, j});
vis[i][j] = true;
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dX[i], ny = y + dY[i];
if (ar <= nx && nx <= br && ac <= ny && ny <= bc && !vis[nx][ny] && !rv[nx][ny]) {
q.push({nx, ny});
vis[nx][ny] = true;
}
}
}
}
}
return cnt;
}
