#include<bits/stdc++.h>
#include "rainbow.h"
#define ll long long
using namespace std;
ll R,C,sr,sc,M,ar,ac,br,bc;
string S;
map<pair<ll,ll>,ll> mp1;
void init(int _R, int _C, int _sr, int _sc, int _M, char *_S){
R=_R; C=_C; sr=_sr; sc=_sc; M=_M; S=string(_S, _S + M);
ll posx=sr,posy=sc;
mp1[{posx,posy}]=1;
for(ll i=0 ; i<M ; i++){
if(S[i]=='S') posx++;
if(S[i]=='N') posx--;
if(S[i]=='E') posy++;
if(S[i]=='W') posy--;
mp1[{posx,posy}]=1;
}
}
bool check(ll x,ll y){
if(mp1.find({x,y})!=mp1.end()) return false;
if(ar<=x and x<=br and ac<=y and y<=bc) return true;
return false;
}
vector<ll> par;
ll root(ll u){
if(par[u]==u) return u;
ll rt=root(par[u]);
par[u]=rt;
return rt;
}
void join(ll u,ll v){
ll ru=root(u);
ll rv=root(v);
par[ru]=rv;
}
int colour(int _ar, int _ac, int _br, int _bc){
ar=_ar; ac=_ac; br=_br; bc=_bc;
ll posx=sr,posy=sc;
map<pair<ll,ll>,ll> mp;
par.clear();
ll cnt=0,i,j,k,p,q;
for(j=-1 ; j<=1 ; j++){
for(k=-1 ; k<=1 ; k++){
if(check(posx+j,posy+k)) mp[{posx+j,posy+k}]=cnt++;
}
}
for(i=0 ; i<M ; i++){
if(S[i]=='S') posx++;
if(S[i]=='N') posx--;
if(S[i]=='E') posy++;
if(S[i]=='W') posy--;
for(j=-1 ; j<=1 ; j++){
for(k=-1 ; k<=1 ; k++){
if(mp.find({posx+j,posy+k})==mp.end() and check(posx+j,posy+k)) mp[{posx+j,posy+k}]=cnt++;
}
}
}
if(cnt==0){
posx=sr,posy=sc;
if(mp1.find({posx,posy})!=mp1.end()) cnt++;
for(i=0 ; i<M ; i++){
if(S[i]=='S') posx++;
if(S[i]=='N') posx--;
if(S[i]=='E') posy++;
if(S[i]=='W') posy--;
if(mp1.find({posx,posy})!=mp1.end()) cnt++;
}
if(cnt) return 0;
return 1;
}
par.resize(cnt);
for(i=0 ; i<cnt ; i++) par[i]=i;
ll pos;
ll pos1=sr,pos2=sc;
ll pos3=sr,pos4=sc;
for(j=-1 ; j<=1 ; j++){
for(k=-1 ; k<=1 ; k++){
for(p=-1 ; p<=1 ; p++){
for(q=-1 ; q<=1 ; q++){
if(abs(pos1+j-pos3-p)+abs(pos2+k-pos4-q)!=1) continue;
if(check(pos1+j,pos2+k) and check(pos3+p,pos4+q)){
join(mp[{pos1+j,pos2+k}],mp[{pos3+p,pos4+q}]);
}
}
}
}
}
for(i=0 ; i<M ; i++){
pos3=pos1;
pos4=pos2;
if(S[i]=='S') pos3++;
if(S[i]=='N') pos3--;
if(S[i]=='E') pos4++;
if(S[i]=='W') pos4--;
for(j=-1 ; j<=1 ; j++){
for(k=-1 ; k<=1 ; k++){
for(p=-1 ; p<=1 ; p++){
for(q=-1 ; q<=1 ; q++){
if(abs(pos1+j-pos3-p)+abs(pos2+k-pos4-q)!=1) continue;
if(check(pos1+j,pos2+k) and check(pos3+p,pos4+q)){
join(mp[{pos1+j,pos2+k}],mp[{pos3+p,pos4+q}]);
}
}
}
}
}
swap(pos1,pos3);
swap(pos2,pos4);
}
set<ll> st;
for(i=0 ; i<cnt ; i++) st.insert(root(i));
return st.size();
}
