#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=_S;
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;
if(check(posx,posy+1)) mp[{posx,posy+1}]=cnt++;
if(check(posx+1,posy)) mp[{posx+1,posy}]=cnt++;
if(check(posx+1,posy+1)) mp[{posx+1,posy+1}]=cnt++;
if(check(posx,posy-1)) mp[{posx,posy-1}]=cnt++;
if(check(posx-1,posy)) mp[{posx-1,posy}]=cnt++;
if(check(posx-1,posy-1)) mp[{posx-1,posy-1}]=cnt++;
if(check(posx-1,posy+1)) mp[{posx-1,posy+1}]=cnt++;
if(check(posx+1,posy-1)) mp[{posx+1,posy-1}]=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(mp.find({posx,posy+1})==mp.end() and check(posx,posy+1)) mp[{posx,posy+1}]=cnt++;
if(mp.find({posx+1,posy})==mp.end() and check(posx+1,posy)) mp[{posx+1,posy}]=cnt++;
if(mp.find({posx+1,posy+1})==mp.end() and check(posx+1,posy+1)) mp[{posx+1,posy+1}]=cnt++;
if(mp.find({posx,posy-1})==mp.end() and check(posx,posy-1)) mp[{posx,posy-1}]=cnt++;
if(mp.find({posx-1,posy})==mp.end() and check(posx-1,posy)) mp[{posx-1,posy}]=cnt++;
if(mp.find({posx-1,posy-1})==mp.end() and check(posx-1,posy-1)) mp[{posx-1,posy-1}]=cnt++;
if(mp.find({posx-1,posy+1})==mp.end() and check(posx-1,posy+1)) mp[{posx-1,posy+1}]=cnt++;
if(mp.find({posx+1,posy-1})==mp.end() and check(posx+1,posy-1)) mp[{posx+1,posy-1}]=cnt++;
}
par.resize(cnt);
for(i=0 ; i<cnt ; i++) par[i]=i;
ll pos1=sr,pos2=sc;
ll pos3,pos4;
for(i=0 ; i<M ; i++){
pos3=pos1;
pos4=pos2;
if(S[i]=='S') pos3=pos1+1;
if(S[i]=='N') pos3=pos1-1;
if(S[i]=='E') pos4=pos2+1;
if(S[i]=='W') pos4=pos2-1;
if(check(pos1-1,pos2) and check(pos3-1,pos4)) join(mp[{pos1-1,pos2}],mp[{pos3-1,pos4}]);
if(check(pos1,pos2+1) and check(pos3,pos4+1)) join(mp[{pos1,pos2+1}],mp[{pos3,pos4+1}]);
if(check(pos1+1,pos2) and check(pos3+1,pos4)) join(mp[{pos1+1,pos2}],mp[{pos3+1,pos4}]);
if(check(pos1,pos2-1) and check(pos3,pos4-1)) join(mp[{pos1,pos2-1}],mp[{pos3,pos4-1}]);
if(check(pos1-1,pos2-1) and check(pos3-1,pos4-1)) join(mp[{pos1-1,pos2-1}],mp[{pos3-1,pos4-1}]);
if(check(pos1-1,pos2+1) and check(pos3-1,pos4+1)) join(mp[{pos1-1,pos2+1}],mp[{pos3-1,pos4+1}]);
if(check(pos1+1,pos2-1) and check(pos3+1,pos4-1)) join(mp[{pos1+1,pos2-1}],mp[{pos3+1,pos4-1}]);
if(check(pos1+1,pos2+1) and check(pos3+1,pos4+1)) join(mp[{pos1+1,pos2+1}],mp[{pos3+1,pos4+1}]);
if(S[i]=='W' or S[i]=='E'){
ll pos=min(pos2,pos4);
if(check(pos1,pos-1) and check(pos1-1,pos-1)) join(mp[{pos1,pos-1}],mp[{pos1-1,pos-1}]);
if(check(pos1+1,pos-1) and check(pos1,pos-1)) join(mp[{pos1+1,pos-1}],mp[{pos1,pos-1}]);
pos=max(pos2,pos4);
if(check(pos1,pos+1) and check(pos1-1,pos+1)) join(mp[{pos1,pos+1}],mp[{pos1-1,pos+1}]);
if(check(pos1+1,pos+1) and check(pos1,pos+1)) join(mp[{pos1+1,pos+1}],mp[{pos1,pos+1}]);
}
else{
ll pos=min(pos1,pos3);
if(check(pos-1,pos2) and check(pos-1,pos2-1)) join(mp[{pos-1,pos2}],mp[{pos-1,pos2-1}]);
if(check(pos-1,pos2) and check(pos-1,pos2+1)) join(mp[{pos-1,pos2}],mp[{pos-1,pos2+1}]);
pos=max(pos1,pos3);
if(check(pos+1,pos2) and check(pos+1,pos2-1)) join(mp[{pos+1,pos2}],mp[{pos+1,pos2-1}]);
if(check(pos+1,pos2) and check(pos+1,pos2+1)) join(mp[{pos+1,pos2}],mp[{pos+1,pos2+1}]);
}
swap(pos1,pos3);
swap(pos2,pos4);
}
set<ll> st;
for(i=0 ; i<cnt ; i++) st.insert(root(i));
if(cnt==0) return 1LL;
else return st.size();
}
