#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200010 * 8;
vector< pair<int,int> > arr , arr2;
vector < int > g[N];
int vis[N] , vi = 0;
int dr[8] = {0 , 1 , 0 , -1 , 1 , 1 , -1 , -1};
int dc[8] = {1 , 0 , -1 , 0 , 1 , -1, 1, -1};
int r1 , c1 , r2 , c2;
inline bool in(int r,int c){
return (r >= r1 && r <= r2 && c >= c1 && c <= c2);
}
void init(int R, int C, int sr, int sc, int M, char *S) {
r1 = 1 , r2 = R , c1 = 1 , c2 = C;
arr2.push_back(make_pair(sr,sc));
int nr , nc , idx;
for(int i = 0;i < M;i++){
if(S[i] == 'N') sr--; else if(S[i] == 'S') sr++; else if(S[i] == 'E') sc++; else sc--;
arr2.push_back(make_pair(sr,sc));
}
sort(arr2.begin(),arr2.end());
arr2.resize(unique(arr2.begin(),arr2.end()) - arr2.begin());
for(int i = 0 ;i < (int)arr2.size();i++){
sr = arr2[i].first;
sc = arr2[i].second;
for(int j = 0 ;j < 8 ;j++){
nr = sr + dr[j];
nc = sc + dc[j];
if(in(nr,nc) && !binary_search(arr2.begin(),arr2.end() , make_pair(nr,nc))){
arr.push_back(make_pair(nr,nc));
}
}
}
sort(arr.begin(),arr.end());
arr.resize(unique(arr.begin(),arr.end()) - arr.begin());
for(int i = 0 ; i < (int)arr.size();i++){
sr = arr[i].first;
sc = arr[i].second;
for(int j = 0 ;j < 4;j++){
nr = sr + dr[j];
nc = sc + dc[j];
idx = lower_bound(arr.begin(),arr.end(),make_pair(nr , nc)) - arr.begin();
if(idx != (int)arr.size() && arr[idx].first == nr && arr[idx].second == nc){
g[i].push_back(idx);
}
}
}
}
void DFS(int node){
vis[node] = vi;
for(int i = 0 ;i < (int)g[node].size();i++){
if(vis[g[node][i]] == vi || !in(arr[g[node][i]].first,arr[g[node][i]].second)) continue;
DFS(g[node][i]);
}
}
int colour(int ar, int ac, int br, int bc) {
r1 = ar , c1 = ac , r2 = br , c2 = bc;
int ans = 0;
vi++;
for(int i = 0 ;i < (int)arr.size();i++){
if(vis[i] == vi || !in(arr[i].first,arr[i].second)) continue;
DFS(i);
ans++;
}
long long sz = (r2 - r1 + 1) * (c2 - c1 + 1);
for(int i = 0 ;i < (int)arr2.size();i++){
if(in(arr2[i].first,arr2[i].second))
sz--;
}
if(ans == 0)
ans = 1;
if(sz == 0)
ans = 0;
return ans;
}
