#include <bits/stdc++.h>
#include "rainbow.h"
using namespace std;
const int maxn = 110;
const int maxm = 202020;
int r, c;
char riv[maxn][maxm];
char vis[maxn][maxm];
int pini[3][maxm], pfim[3][maxm];
int soma1 = 0, soma2 = 0;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
void dfs(int x, int y, int x1, int y1, int x2, int y2)
{
vis[x][y] = 1;
for (int i = 0; i < 4; i++) {
int xx = x+dx[i];
int yy = y+dy[i];
if (xx < x1 or xx > x2 or yy < y1 or yy > y2) continue;
if (riv[xx][yy] or vis[xx][yy]) continue;
dfs(xx, yy, x1, y1, x2, y2);
}
}
void init2()
{
for (int i = 1; i <= c; i++) {
if (!riv[1][i] and (i == 1 or riv[1][i-1]))
pini[1][i]++;
if (!riv[2][i] and (i == 1 or riv[2][i-1]))
pini[2][i]++;
if (!riv[1][i] and (i==c or riv[1][i+1]))
pfim[1][i]++;
if (!riv[2][i] and (i==c or riv[2][i+1]))
pfim[2][i]++;
if ((pini[1][i] and pini[2][i]) or
((riv[1][i]^riv[2][i]) and (pini[1][i]|pini[2][i])))
pini[0][i]++;
if ((pfim[1][i] and pfim[2][i]) or
((riv[1][i]^riv[2][i]) and (pfim[1][i]|pfim[2][i])))
pfim[0][i]++;
pini[1][i] += pini[1][i-1];
pini[2][i] += pini[2][i-1];
pfim[1][i] += pfim[1][i-1];
pfim[2][i] += pfim[2][i-1];
pini[0][i] += pini[0][i-1];
pfim[0][i] += pfim[0][i-1];
}
// for (int i = 1; i <= c; i++)
// cout << pini[1][i]-pini[1][i-1] << " ";
// cout << "\n";
// for (int i = 1; i <= c; i++)
// cout << pini[2][i]-pini[2][i-1] << " ";
// cout << "\n";
// for (int i = 1; i <= c; i++)
// cout << pini[0][i]-pini[0][i-1] << " ";
// cout << "\n";
}
void init(int rr, int cc, int sr, int sc, int m, char* s)
{
r = rr, c = cc;
int x = sr, y = sc;
riv[x][y] = 1;
for (int i = 0; i < m; i++) {
if (s[i] == 'N') x--;
else if (s[i] == 'E') y++;
else if (s[i] == 'S') x++;
else y--;
riv[x][y] = 1;
}
if (r == 2)
init2();
}
int colour1(int x1, int y1, int x2, int y2)
{
int ans = 0;
for (int i = x1; i <= x2; i++)
for (int j = y1; j <= y2; j++)
vis[i][j] = 0;
for (int i = x1; i <= x2; i++)
for (int j = y1; j <= y2; j++)
if (!riv[i][j] and !vis[i][j])
dfs(i, j, x1, y1, x2, y2), ans++;
return ans;
}
int colour2(int x1, int y1, int x2, int y2)
{
if (y2 == 1) {
int ans = pini[1][x2] - pfim[1][x1-1];
return ans;
}
if (y1 == 2) {
int ans = pini[2][x2] - pfim[2][x1-1];
return ans;
}
return pini[0][x2]-pfim[0][x1-1];
}
int colour(int x1, int y1, int x2, int y2)
{
if (r == 2 and c > 50)
return colour2(x1, y1, x2, y2);
else return colour1(x1, y1, x2, y2);
}
