#include "rainbow.h"
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
struct UF {
vector<int> U, R;
int C;
UF(int N) {
rep(i, N) U.pb(i), R.pb(1);
C = N;
}
int find(int x) {
if (U[x]==x)return x;
return U[x]=find(U[x]);
}
void unite(int x, int y) {
x=find(x), y=find(y);
if (x==y)return;
if (R[x]<R[y])swap(x,y);
U[y]=x;
R[x]+=R[y];
C--;
}
};
bool bad[50][50];
int id[50][50];
void init(int H, int W, int sr, int sc, int M, char *S) {
if (W > 50 || H > 50) abort();
int y = sr-1, x = sc-1;
bad[x][y] = true;
rep(i, M) {
if (S[i] == 'N') y--;
if (S[i] == 'S') y++;
if (S[i] == 'W') x--;
if (S[i] == 'E') x++;
bad[x][y] = true;
}
}
int colour(int ar, int ac, int br, int bc) {
ar--, ac--, br--, bc--;
int V = 0;
for (int x=ac; x<=bc; x++) {
for (int y=ar; y<=br; y++) {
if (!bad[x][y]) id[x][y] = V++;
else id[x][y] = -1;
}
}
UF uf(V);
for (int x=ac; x<=bc; x++) {
for (int y=ar; y<=br; y++) {
if (x+1<=bc && !bad[x][y] && !bad[x+1][y]) uf.unite(id[x][y], id[x+1][y]);
if (y+1<=br && !bad[x][y] && !bad[x][y+1]) uf.unite(id[x][y], id[x][y+1]);
}
}
return uf.C;
}
