#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
// V - E + F = 1 + C ? V - E + F = 3 - C
set<pii> river;
set<pii> fc;
map<pii, int> relabel;
int cc = 0;
class dsu{
public:
int fd(int x , bool isr){
if(!pai.count(x)){
peso[x] = 1;
if(!isr)
c++;
return pai[x] = x;
}
return pai[x] == x ? x : pai[x] = fd(pai[x] , isr);
}
void join(int u , int v , bool isr){
if(fd(u,isr) == fd(v,isr)) return;
u = fd(u,isr) , v = fd(v,isr);
if(!isr)
c--;
if(peso[u] > peso[v]) swap(u,v);
pai[u] = v , peso[v] += peso[u];
}
int get_c(){
return c;
}
private:
map<int,int> pai, peso;
int c = 0;
};
int RR , CC;
void init(int R, int C, int sr, int sc, int M, char *S) {
river.insert(pii(sr , sc));
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 --;
river.insert(pii(sr , sc));
if(!relabel.count(pii(sr , sc))){
relabel[pii(sr,sc)] = ++ cc;
}
}
RR = R , CC = C;
}
int dx[4] = {0 , 1 , 0 , -1};
int dy[4] = {1 , 0 , -1 , 0};
int colour(int ar, int ac, int br, int bc) {
dsu T;
// set<pii> parte;
// fc.clear();
// for(auto w : river){
// if(ar <= w.F && w.F <= br && ac <= w.S && w.S <= bc){
// T.fd(relabel[w] , 1);
// parte.insert(w);
// }
// }
// for(auto w : parte){
// for(int j = 0 ; j < 4 ; j ++){
// int u = w.F + dx[j] , v = w.S + dy[j];
// if(ar <= u && u <= br && ac <= v && v <= bc){
// if(!relabel[pii(u,v)]){
// relabel[pii(u,v)] = ++cc;
// }
// if(parte.count(pii(u,v))) T.join(relabel[pii(u,v)] , relabel[w] , 1);
// else{
// T.fd(relabel[pii(u,v)] , 0);
// fc.insert(pii(u,v));
// }
// }
// }
// }
// for(auto w : fc){
// for(int j = 0 ; j < 4 ; j++){
// int u = w.F + dx[j] , v = w.S + dy[j];
// if(ar <= u && u <= br && ac <= v && v <= bc){
// if(fc.count(pii(u,v))){
// T.join(relabel[pii(u,v)] , relabel[w] , 0);
// }
// }
// }
// }
for(int i = ar ; i <= br ; i ++){
for(int j = ac ; j <= bc ;j ++){
if(!relabel[pii(i,j)]) relabel[pii(i,j)] = ++ cc;
T.fd(relabel[pii(i,j)] , river.count(pii(i,j)));
}
}
for(int i = ar ; i <= br ; i ++){
for(int j = ac ; j <= bc ;j ++){
for(int k = 0 ; k < 4 ; k ++){
int u = i + dx[k] , v = j + dy[k];
if(ar <= u && u <= br && ac <= v && v <= bc){
if(river.count(pii(u , v)) == river.count(pii(i,j))){
T.join(relabel[pii(u,v)], relabel[pii(i , j)] , river.count(pii(u,v)));
}
}
}
}
}
return (T.get_c() );
}
// #define int int
