#include "rainbow.h"
#include <bits/stdc++.h>
#define N 200050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;
int n, m, ok[5][N], block[5][N];
int inicio[5][N];
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
int Ni, Mi, Nii, Mii, col;
int branco[2][N];
int dxy(char c)
{
if(c == 'N') return 1;
if(c == 'S') return 0;
if(c == 'W') return 3;
if(c == 'E') return 2;
return -1;
}
int pref[5][N];
void dfs(int x, int y)
{
ok[x][y] = 1;
//cout<<"DFS "<<x<<" "<<y<<"\n";
for(int i = 0; i < 4; i++)
{
int a = x + dx[i], b = y + dy[i];
if(a < Ni or b < Mi or a > Nii or b > Mii or ok[a][b] == 1 or block[a][b]) continue;
ok[a][b] = 1;
dfs(a, b);
}
}
vector < pii > zeros;
int ans[5][N];
int colmin = N, colmax = 0;
void init(int R, int C, int sr, int sc, int M, char *S)
{
int x = sr, y = sc;
col = C;
string s;
block[x][y] = 1;
for(int i = 0; i < M; i++) s.push_back(S[i]);
for(int i = 0; i < s.size(); i++)
{
block[x][y] = 1;
int id = dxy(s[i]);
if(id == -1) break;
x = x + dx[id], y = y + dy[id];
block[x][y] = 1;
//cout<<"BLOCK "<<s.size()<<" "<<x<<" "<<y<<"\n";
}
for(int i = 1; i <= 2; i++)
for(int j = 1; j <= C; j++)
pref[i][j] = pref[i][j - 1] + block[i][j];
for(int i = 1; i <= 2; i++)
{
for(int j = 1; j <= C; j++)
{
if(block[i][j]) pref[i][j] = pref[i][j - 1];
else pref[i][j] = 1 + pref[i][j - 1];
}
}
for(int i = 1; i <= 2; i++)
{
for(int j = 1; j <= C; j++)
{
int st = j, entrou = 0;
while(!block[i][j] and j <= C) j++, entrou = 1;
if(entrou) j--;
if(!block[i][st])
{
zeros.push_back({st, j});
ans[i][st] ++;
inicio[i][st] = 1;
//cout<<"ADD "<<i<<", "<<st<<"\n";
//ans[i][j] --;
}
}
}
for(int i = 1; i <= 2; i++)
for(int j = 1; j <= col; j++) ans[i][j] += ans[i][j - 1];
for(int i = 1; i <= 2; i++)
{
for(int j = 1; j <= C; j++)
{
if(block[i][j] == 1)
{
colmax = max(colmax, j);
colmin = min(colmin, j);
}
}
}
}
int colour(int ar, int ac, int br, int bc)
{
int cnt = 0;
if(ar == br)
{
if(!block[ar][ac - 1] and ac > 1 and !block[ar][ac ]) return 1 + ans[ar][bc] - ans[ar][ac - 1];
else return ans[ar][bc] - ans[ar][ac - 1];
}
else
{
int dA = 0, dB = 0;
if(block[1][colmin] and block[2][colmin] and ac < colmin) dA ++;
if(block[1][colmax] and block[2][colmax] and bc > colmax) dB ++;
//cout<<"DELTA "<<dA<<" "<<dB<<'\n';
ac = max(ac, colmin);
bc = min(bc, colmax);
if(!block[1][ac - 1] and ac > 1 and !block[1][ac ]) dA += 1 + ans[1][bc] - ans[1][ac - 1];
else dA += ans[1][bc] - ans[1][ac - 1];
// cout<<"DELTA LINHA 1 "<<colmin<<" "<<colmax<<" "<<dA<<"\n";
if(!block[2][ac - 1] and ac > 1 and !block[2][ac ]) dA += 1 + ans[2][bc] - ans[2][ac - 1];
else dA += ans[2][bc] - ans[2][ac - 1];
/// cout<<"DELTA LINHA 2 "<<colmin<<" "<<colmax<<" "<<dA<<"\n";
return dA + dB;
}
}
