#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
const int N = 200005;
const int xx[4] = {-1, 1, 0, 0};
const int yy[4] = {0, 0, -1, 1};
const char cc[4] = {'N', 'S', 'W', 'E'};
int n, m;
set<pair<int, int> > s;
int minx, maxx, miny, maxy;
set<pair<int, int> > c;
void dfs(int x, int y, int x1, int y1_, int x2, int y2)
{
if (!(x1 <= x && x <= x2))
return;
if (!(y1_ <= y && y <= y2))
return;
if (s.find(m_p(x, y)) != s.end())
return;
if (c.find(m_p(x, y)) != c.end())
return;
c.insert(m_p(x, y));
minx = min(minx, x);
maxx = max(maxx, x);
miny = min(miny, y);
maxy = max(maxy, y);
for (int i = 0; i < 4; ++i)
{
int hx = x + xx[i];
int hy = y + yy[i];
dfs(hx, hy, x1, y1_, x2, y2);
}
}
vector<int> ul[3], ur[3];
void init(int R, int C, int sx, int sy, int ss, char *s)
{
n = R;
m = C;
vector<pair<int, int> > v;
v.push_back(m_p(sx, sy));
for (int i = 0; i < ss; ++i)
{
for (int j = 0; j < 4; ++j)
{
if (cc[j] == s[i])
{
v.push_back(m_p(v.back().fi + xx[j], v.back().se + yy[j]));
}
}
}
for (int i = 0; i < v.size(); ++i)
{
::s.insert(v[i]);
}
if (n == 2)
{
for (int j = 1; j <= m; ++j)
{
for (int i = 1; i <= n; ++i)
{
if (c.find(m_p(i, j)) == c.end())
{
minx = maxx = i;
miny = maxy = j;
dfs(i, j, 1, 1, 2, m);
ul[0].push_back(miny);
ur[0].push_back(maxy);
}
}
}
for (int i = 1; i <= 2; ++i)
{
for (int j = 1; j <= n; ++j)
{
if (::s.find(m_p(i, j)) == ::s.end())
{
if (j == 1 || ::s.find(m_p(i, j - 1)) != ::s.end())
{
ul[i].push_back(j);
}
if (j == m || ::s.find(m_p(i, j + 1)) != ::s.end())
{
ur[i].push_back(j);
}
}
}
}
}
/*minx = maxx = sx;
miny = maxy = sy;
for (int i = 0; i < v.size(); ++i)
{
minx = min(minx, v[i].fi);
maxx = max(maxx, v[i].fi);
miny = min(miny, v[i].se);
maxy = max(maxy, v[i].se);
}*/
}
int colour(int x1, int y1_, int x2, int y2)
{
/*if (max(x1, minx) > min(x2, maxx))
return 0;
if (max(y1_, miny) > max(y2, maxy))
return 0;*/
/*x1 = max(x1, minx - 2);
x2 = min(x2, maxx + 2);
y1_ = max(y1_, miny - 2);
y2 = min(y2, maxy + 2);*/
if (n == 2)
{
int z;
if (x1 < x2)
z = 0;
else
z = x1;
int l = upper_bound(all(ul[z]), y2) - ul[z].begin();
int r = lower_bound(all(ur[z]), y1_) - ur[z].begin();
if (l > r)
return 0;
return r - l + 1;
}
c.clear();
int ans = 0;
for (int x = x1; x <= x2; ++x)
{
for (int y = y1_; y <= y2; ++y)
{
if (s.find(m_p(x, y)) != s.end())
continue;
if (c.find(m_p(x, y)) == c.end())
{
++ans;
dfs(x, y, x1, y1_, x2, y2);
}
}
}
return ans;
}
