#include <bits/stdc++.h>
#include "rainbow.h"
#define ll long long
#define ll1 long long
#define ull unsigned long long
#define dou long double
#define str string
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define vbool vector<bool>
#define vstr vector<str>
#define vvll vector<vll>
#define pb push_back
#define pf push_front
#define endl "\n"
#define fr first
#define se second
// #define sortcmp(a) sort(a.begin(), a.end(), cmp)
#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
//using namespace __gnu_pbds;
const ll INF = 1e18;
const int lg = 20;
mt19937 rng(time(0));
ll randll(ll l, ll r){
return uniform_int_distribution<ll>(l, r)(rng);
}
map<ll, vpll> mp;
ll n, m;
vll pr, sz;
ll find(ll v){
if(pr[v] == v) return v;
return pr[v] = find(pr[v]);
}
void unite(ll a, ll b){
a = find(a);
b = find(b);
if(a == b) return;
if(sz[a] < sz[b]){
pr[a] = b;
sz[b] += sz[a];
}
else{
pr[b] = a;
sz[a] += sz[b];
}
}
void init(int N, int M, int x, int y, int k, char *s) {
map<ll, vll> m1;
n = N, m = M;
m1[x].pb(y);
for(int i = 0; i < k; i ++){
if(s[i] == 'N') x --;
else if(s[i] == 'S') x ++;
else if(s[i] == 'W') y --;
else y ++;
m1[x].pb(y);
}
for(auto i : m1){
sort(i.se);
ll l = i.se[0];
for(int j = 1; j < i.se.size(); j ++){
if(i.se[j]-1 <= l) continue;
mp[i.fr].pb({l, i.se[j-1]});
l = i.se[j];
}
mp[i.fr].pb({l, i.se.back()});
}
}
int colour(int x, int y, int xr, int yr) {
ll res = 0, k = 0;
vpll v;
vll b1;
for(int i = x; i <= xr; i ++){
vpll v1;
pll x = {-1, -1};
vpll p = mp[i];
for(int j = 0; j < p.size(); j ++){
if(p[j].se < y || p[j].fr > yr) continue;
if(x.fr == -1){
if(p[j].fr > y) v1.pb({y, p[j].fr-1});
}
else{
v1.pb({x.se+1, p[j].fr-1});
}
x = {max((ll)y, p[j].fr), min((ll)yr, p[j].se)};
}
if(x.fr == -1) v1.pb({y, yr});
else if(x.se < yr) v1.pb({x.se+1, yr});
vll b(v1.size());
ll l = 0;
for(int j = 0; j < v1.size(); j ++){
sz.pb(1);
pr.pb(k);
b[j] = k ++;
while(l < v.size()){
if(v[l].se < v1[j].fr){
l ++;
continue;
}
if(v[l].fr > v1[j].se) break;
unite(b[j], b1[l]);
if(v[l].se <= v1[j].se){
l ++;
}
else break;
}
}
b1 = b;
v = v1;
}
set<ll> s;
for(int i = 0; i < k; i ++){
s.insert(find(i));
}
sz.clear();
pr.clear();
return s.size();
}
