#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define info() cerr << __PRETTY_FUNCTION__ << ": " << __LINE__ << endl
void abc() {cerr << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cerr << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << '(' << a.X << ", " << a.Y << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
return o << '}';
}
template <typename T> struct vv : vector <vector <T>> {
vv(int n, int m, T v) : vector <vector <T>> (n, vector <T>(m, v)) {}
vv() {}
};
template <typename T> struct vvv : vector <vv <T>> {
vvv(int n, int m, int k, T v) : vector <vv <T>> (n, vv <T>(m, k, v)) {}
vvv() {}
};
#ifdef Doludu
#define test(args...) info(), abc("[" + string(#args) + "]", args)
#define owo
#include "rainbow-grader.cpp"
#else
#define test(args...)
#define owo ios::sync_with_stdio(false); cin.tie(0)
#endif
// const int mod = 998244353, N = 1000001, logN = 20, K = 111;
vv <bool> area;
int n, m;
void init(int _n, int _m, int r, int c, int k, char *s) {
r--, c--;
n = _n, m = _m;
area = vv<bool>(n, m, false);
area[r][c] = true;
for (int i = 0; i < k; ++i) {
if (s[i] == 'W') c--;
if (s[i] == 'E') c++;
if (s[i] == 'N') r--;
if (s[i] == 'S') r++;
area[r][c] = true;
}
}
int colour(int l1, int r1, int l2, int r2) {
l1--, r1--;
vv <bool> vis = area;
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
function<void(int, int)> bfs = [&](int a, int b) {
queue <pii> q;
q.emplace(a, b);
vis[a][b] = true;
while (!q.empty()) {
int x, y;
tie(x, y) = q.front(); q.pop();
test(x, y);
for (int k = 0; k < 4; ++k) {
int nx = x + dx[k], ny = y + dy[k];
if (l1 <= nx && nx < l2 && r1 <= ny && ny < r2) if (!vis[nx][ny]) {
vis[nx][ny] = true;
q.emplace(nx, ny);
}
}
}
};
int ans = 0;
for (int i = l1; i < l2; ++i) for (int j = r1; j < r2; ++j) {
if (vis[i][j]) continue;
bfs(i, j);
ans++;
}
return ans;
}
/*
6 4 9 4
3 3
NWESSWEWS
2 3 2 3
3 2 4 4
5 3 6 4
1 2 5 3
*/
