#include <bits/stdc++.h>
#include "rainbow.h"
using namespace std;
vector<pair<int,int>> pts;
void init(int R, int C, int sr, int sc, int M, char *S) {
pts.push_back({sr,sc});
for(int i = 0;i < M;i++){
if(S[i] == 'N'){
sr--;
}else if(S[i] == 'S'){
sr++;
}else if(S[i] == 'W'){
sc--;
}else{
sc++;
}
assert(sr <= R && sr >= 1);
assert(sc <= C && sc >= 1);
pts.push_back({sr,sc});
}
sort(pts.begin(),pts.end());
pts.resize(unique(pts.begin(),pts.end()) - pts.begin());
}
map<pair<int,int>,bool> k,vis;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
int colour(int ar, int ac, int br, int bc) {
// V - E + F = 1 + C -> F = 1 + C - V + E
k.clear();
vis.clear();
int V = 0,E = 0;
bool ok =true;
for(auto [r,c]:pts){
if(r >= ar && r <= br && c >= ac && c <= bc){
k[{r,c}] = 1;
if(r == ar || r == br || c == ac || c == bc){
ok=false;
}
}
}
if(k.empty()){
ok=false;
}
for(int i = ar - 1;i <= br + 1;i++){
k[{i,ac-1}] = k[{i,bc+1}] = 1;
}
for(int i = ac - 1;i <= bc + 1;i++){
k[{ar-1,i}] = k[{br+1,i}] = 1;
}
int bf = 0;
for(auto [xx,_y]:k){
auto [r,c] = xx;
if(k.count({r + 1,c}) && k.count({r,c + 1}) && k.count({r + 1,c + 1})){
bf++;
}
if(k.count({r+1,c+1}) && !k.count({r+1,c}) && !k.count({r,c+1})){
E += 2;
}
if(k.count({r+1,c-1}) && !k.count({r+1,c}) && !k.count({r,c-1})){
E += 2;
}
if(!vis.count({r,c})){
queue<pair<int,int>> q;
q.push({r,c});
vis[{r,c}]=1;
while(!q.empty()){
V++;
auto [x,y] = q.front();q.pop();
// cout << x << ' ' << y << '\n';
for(int i = 0;i < 4;i++){
int _x = x + dx[i],_y = y + dy[i];
if(k.count({_x,_y})){
E++;
}
if(k.count({_x,_y}) && !vis.count({_x,_y})){
vis[{_x,_y}]=1;
q.push({_x,_y});
}
}
}
}
}
assert(E%2==0);
E /= 2;
return -V + E - bf + 1+ok;
}
