#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU{
int n;
vector<int> lab;
int cc;
void init(int _n){
n=_n;
cc=n;
lab.assign(n+1, -1);
}
int find_set(int u){
return lab[u]<0?u:lab[u]=find_set(lab[u]);
}
void union_sets(int u, int v){
u=find_set(u), v=find_set(v);
if (u!=v){
if (lab[u]>lab[v]) swap(u, v);
lab[u]+=lab[v];
lab[v]=u;
--cc;
}
}
} dsu, dsu1, dsu2;
const int N=2e5+10;
const int dx[]={1, -1, 0, 0}, dy[]={0, 0, 1, -1};
bool a[100][100], a2[3][N];
int pf[3][N], pf1[N], pf2[N];
int r, c;
void init(int R, int C, int sr, int sc, int M, char *S) {
if (R==2){
r=R, c=C;
a2[sr][sc]=1;
for (int i=0; i<M; ++i){
if (S[i]=='N') --sr;
if (S[i]=='S') ++sr;
if (S[i]=='E') ++sc;
if (S[i]=='W') --sc;
a2[sr][sc]=1;
}
dsu.init(r*c);
for (int i=1; i<=r; ++i) for (int j=1; j<=c; ++j){
if (!a2[i][j]){
for (int k=0; k<4; ++k){
int x=i+dx[k], y=j+dy[k];
if (x<1 || y<1 || x>r || y>c || a2[x][y]) continue;
dsu.union_sets((i-1)*c+(j-1), (x-1)*c+(y-1));
}
}
}
dsu1.init(c), dsu2.init(c);
for (int j=1; j<=c; ++j){
if (!a2[1][j]){
for (int k=2; k<4; ++k){
int x=1, y=j+dy[k];
if (y<1 || y>c || a2[x][y]) continue;
dsu1.union_sets(j-1, y-1);
}
}
}
for (int j=1; j<=c; ++j){
if (!a2[2][j]){
for (int k=2; k<4; ++k){
int x=2+dx[k], y=j+dy[k];
if (y<1 || y>c || a2[x][y]) continue;
dsu2.union_sets(j-1, y-1);
}
}
}
for (int i=1; i<=r; ++i) for (int j=1; j<=c; ++j){
pf[i][j]=pf[i][j-1];
if (!a2[i][j] && dsu.lab[(i-1)*c+j-1]<0) ++pf[i][j];
}
for (int i=1; i<=c; ++i){
pf1[i]=pf1[i-1];
if (!a2[1][i] && dsu1.lab[i-1]<0) ++pf1[i];
}
for (int i=1; i<=c; ++i){
pf2[i]=pf2[i-1];
if (!a2[2][i] && dsu2.lab[i-1]<0) ++pf2[i];
}
}else{
r=R, c=C;
a[sr][sc]=1;
for (int i=0; i<M; ++i){
if (S[i]=='N') --sr;
if (S[i]=='S') ++sr;
if (S[i]=='E') ++sc;
if (S[i]=='W') --sc;
a[sr][sc]=1;
}
}
}
int colour(int ar, int ac, int br, int bc) {
if (r==2){
set<int> st;
int ans=0;
if (ar==br && ar==1){
ans=pf1[bc]-pf1[ac-1];
if (!a2[ar][ac] && dsu1.find_set(ac-1)>=0) st.insert(dsu1.find_set(ac-1));
if (!a2[ar][bc] && dsu1.find_set(bc-1)>=0) st.insert(dsu1.find_set(bc-1));
for (int i:st) if (i<ac-1 || i>bc-1) ++ans;
}else if (ar==br){
ans=pf2[bc]-pf2[ac-1];
if (!a2[ar][ac] && dsu2.find_set(ac-1)>=0) st.insert(dsu2.find_set(ac-1));
if (!a2[ar][bc] && dsu2.find_set(bc-1)>=0) st.insert(dsu2.find_set(bc-1));
for (int i:st) if (i<ac-1 || i>bc-1) ++ans;
}else{
ans=pf[1][bc]-pf[1][ac-1]+pf[2][bc]-pf[2][ac-1];
if (!a2[ar][ac] && dsu.find_set(ac-1)>=0) st.insert(dsu.find_set(ac-1));
if (!a2[ar][bc] && dsu.find_set(bc-1)>=0) st.insert(dsu.find_set(bc-1));
if (!a2[br][ac] && dsu.find_set(c+ac-1)>=0) st.insert(dsu.find_set(c+ac-1));
if (!a2[br][bc] && dsu.find_set(c+bc-1)>=0) st.insert(dsu.find_set(c+bc-1));
for (int i:st) if ((i%c<ac-1 || i%c>bc-1)) ++ans;
}
return ans;
}
dsu.init((br-ar+1)*(bc-ac+1));
for (int i=ar; i<=br; ++i) for (int j=ac; j<=bc; ++j){
if (a[i][j]) --dsu.cc;
else{
for (int k=0; k<4; ++k){
int x=i+dx[k], y=j+dy[k];
if (x<ar || y<ac || x>br || y>bc || a[x][y]) continue;
dsu.union_sets((i-ar)*(bc-ac+1)+(j-ac), (x-ar)*(bc-ac+1)+(y-ac));
}
}
}
return dsu.cc;
}
