#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200'000;
const int D = 4;
const int DX[D] = {0, 0, -1, 1};
const int DY[D] = {-1, 1, 0, 0};
int n, m, a, b, x1, yyy, x2, y2;
vector<pair<int, int>> path;
vector<char> vecDir = {'W', 'E', 'N', 'S'};
int markSub1[60][60];
void uniquePath() {
sort(path.begin(), path.end());
path.resize(unique(path.begin(), path.end()) - path.begin());
}
bool isSub1() {
return max(n, m) <= 50;
}
bool inPath(int x, int y) {
int idx = lower_bound(path.begin(), path.end(), make_pair(x, y)) - path.begin();
return idx < path.size() && path[idx] == make_pair(x, y);
}
bool inSub(int a, int b) {
bool checkA = (x1 <= a && a <= x2);
bool checkB = (yyy <= b && b <= y2);
return checkA && checkB;
}
void initSub1() {
uniquePath();
}
void init(int R, int C, int sr, int sc, int M, char *S) {
n = R;
m = C;
a = sr;
b = sc;
path.push_back({a, b});
for (int i = 0; i < M; i++) {
int idx;
for (int j = 0; j < D; j++)
if (S[i] == vecDir[j])
idx = j;
int nx = path.back().first + DX[idx];
int ny = path.back().second + DY[idx];
path.push_back({nx, ny});
}
if (isSub1())
initSub1();
}
void dfs(int i, int j) {
markSub1[i][j] = true;
for (int d = 0; d < D; d++) {
int nx = i + DX[d];
int ny = j + DY[d];
if (inSub(nx, ny) && !inPath(nx, ny) && !markSub1[nx][ny])
dfs(nx, ny);
}
}
int solveSub1() {
for (int i = x1; i <= x2; i++)
for (int j = yyy; j <= y2; j++)
markSub1[i][j] = 0;
int ans = 0;
for (int i = x1; i <= x2; i++)
for (int j = yyy; j <= y2; j++)
if (!inPath(i, j) && !markSub1[i][j]) {
ans++;
dfs(i, j);
}
return ans;
}
int colour(int ar, int ac, int br, int bc) {
x1 = ar;
yyy = ac;
x2 = br;
y2 = bc;
if (isSub1())
return solveSub1();
return 0;
}
