#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
vector< int > arr[N];
int n , m;
int cnt = 0 , dsu[N];
int Find(int u){
return (u == dsu[u] ? u : dsu[u] = Find(dsu[u]));
}
void init(int R, int C, int sr, int sc, int M, char *S) {
n = R, m = C;
arr[sr].push_back(sc);
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--;
arr[sr].push_back(sc);
}
for(int i = 1;i <= R;i++){
sort(arr[i].begin(),arr[i].end());
arr[i].resize(unique(arr[i].begin(),arr[i].end()) - arr[i].begin());
}
}
int colour(int ar, int ac, int br, int bc) {
int ans = 0 , a , b, j;
vector< pair<int,int> > pre , cur;
for(int i = ar ;i <= br;i++){
j = lower_bound(arr[i].begin(),arr[i].end(), ac) - arr[i].begin();
a = ac - 1;
while(j < (int)arr[i].size() && arr[i][j] <= bc){
if(a + 1 <= arr[i][j] - 1){
cur.push_back(make_pair(a + 1 , arr[i][j] - 1));
}
a = arr[i][j];
j++;
}
if(a + 1 <= bc) cur.push_back(make_pair(a + 1, bc));
ans += (int)cur.size();
for(j = 0 ;j < (int)cur.size();j++){
dsu[cnt + j] = cnt + j;
}
j = 0;
for(int i = 0;i < (int)cur.size();i++){
while(j < (int)pre.size() && pre[j].second < cur[i].first) j++;
while(j < (int)pre.size() && pre[j].first <= cur[i].second){
a = Find(cnt - (int)pre.size() + j);
b = Find(cnt + i);
if(a != b){
ans--;
dsu[a] = b;
}
j++;
}
if(j)
j--;
}
cnt += (int)cur.size();
pre = cur;
cur.clear();
}
return ans;
}
