#include <bits/stdc++.h>
#include "rainbow.h"
std::vector<std::vector<bool> > map_raw;
std::vector<std::pair<int, int> > blanks;
std::vector<std::pair<int, int> > blanks0;
std::vector<std::pair<int, int> > blanks1;
bool flag0 = false;
void init(int h, int w, int sx, int sy, int m, char *s) {
sx--;
sy--;
auto create_raw = [&] () {
map_raw.resize(h, std::vector<bool>(w, true));
int x = sx;
int y = sy;
map_raw[x][y] = false;
for (int i = 0; i < m; i++) {
if (s[i] == 'N') x--;
if (s[i] == 'S') x++;
if (s[i] == 'W') y--;
if (s[i] == 'E') y++;
map_raw[x][y] = false;
}
};;
if (h <= 50 && w <= 50) {
create_raw();
}
if (h == 2) {
create_raw();
{
int last = -1;
int prev = 0;
for (int i = 0; i <= w; i++) {
int cur = i < w ? (map_raw[0][i] | ((int) map_raw[1][i] << 1)) : 0;
// std::cerr << "! " << cur << " " << prev << std::endl;
if (prev & cur) {
prev = cur;
continue;
}
if (prev) blanks.push_back({last, i - 1});
if (cur) last = i;
prev = cur;
}
}
for (int i = 0; i < 2; i++) {
for (int j = 0; j < w; ) {
if (!map_raw[i][j]) j++;
else {
int t = j;
while (j < w && map_raw[i][j]) j++;
(i ? blanks1 : blanks0).push_back({t, j - 1});
}
}
}
flag0 = true;
}
}
int colour(int x0, int y0, int x1, int y1) {
/*
for (auto i : blanks) std::cerr << i.first << "," << i.second << " ";
std::cerr << std::endl;
for (auto i : blanks0) std::cerr << i.first << "," << i.second << " ";
std::cerr << std::endl;
for (auto i : blanks1) std::cerr << i.first << "," << i.second << " ";
std::cerr << std::endl;*/
x0--;
y0--;
if (flag0) {
auto &target = x1 == 1 ? blanks0 : x0 == 1 ? blanks1 : blanks;
auto itr0 = std::lower_bound(target.begin(), target.end(), std::pair<int, int>{y0, -1});
if (itr0 != target.begin() && std::prev(itr0)->second >= y0) itr0--;
auto itr1 = std::lower_bound(target.begin(), target.end(), std::pair<int, int>{y1, -1});
return itr1 - itr0;
} else if (map_raw.size()) {
std::vector<std::vector<bool> > used(map_raw.size(), std::vector<bool>(map_raw[0].size()));
std::queue<std::pair<int, int> > que;
int res = 0;
for (int x = x0; x < x1; x++) for (int y = y0; y < y1; y++) if (!used[x][y] && map_raw[x][y]) {
used[x][y] = true;
res++;
que.push({x, y});
while (que.size()) {
auto i = que.front();
que.pop();
std::pair<int, int> dd[] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
for (auto d : dd) {
int x = i.first + d.first;
int y = i.second + d.second;
if (x < x0 || x >= x1 || y < y0 || y >= y1) continue;
if (!map_raw[x][y] || used[x][y]) continue;
used[x][y] = true;
que.push({x, y});
}
}
}
return res;
}
return 0;
}
