#include "rainbow.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
const int N = 2e5 + 5;
struct MSST{
vector<int> tree[N << 2];
void add(int i, int y, int lx = 0, int rx = N, int x = 1){
tree[x].push_back(y);
if(lx == rx) return;
int m = (lx + rx) >> 1;
if(i <= m) add(i, y, lx, m, x<<1);
else add(i, y, m+1, rx, x<<1|1);
}
void build(int lx = 0, int rx = N, int x = 1){
tree[x].push_back(-1);
tree[x].push_back(N);
sort(tree[x].begin(), tree[x].end());
if(lx == rx) return;
int m = (lx + rx) >> 1;
build(lx, m, x<<1), build(m+1, rx, x<<1|1);
}
int get(int l, int r, int l_, int r_, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return 0;
if(lx >= l && rx <= r){
auto R = upper_bound(tree[x].begin(), tree[x].end(), r_);
auto L = lower_bound(tree[x].begin(), tree[x].end(), l_);
return R - L;
} int m = (lx + rx) >> 1;
return get(l, r, l_, r_, lx, m, x<<1) + get(l, r, l_, r_, m+1, rx, x<<1|1);
}
}ed[2], ver, sq; //, ver, sq;
vector<int> row[N], col[N], erow[N], ecol[N];
set<ar<int, 2>> ss, tot, is[2];
void init(int n, int m, int x, int y, int k, char *s) {
ss.insert({x, y});
for(int i=0;i<k;i++){
if(s[i] == 'N') x--;
if(s[i] == 'S') x++;
if(s[i] == 'W') y--;
if(s[i] == 'E') y++;
ss.insert({x, y});
}
for(auto x : ss){
//~ cout<<x[0]<<" "<<x[1]<<"\n";
is[0].insert(x);
is[0].insert({x[0] + 1, x[1]});
is[1].insert(x);
is[1].insert({x[0], x[1] + 1});
tot.insert(x);
tot.insert({x[0] + 1, x[1]});
tot.insert({x[0], x[1] + 1});
tot.insert({x[0] + 1, x[1] + 1});
sq.add(x[0], x[1]);
}
for(auto x : tot){
if(is[0].count(x)) ed[0].add(x[0], x[1]), erow[x[0]].push_back(x[1]);
if(is[1].count(x)) ed[1].add(x[0], x[1]), ecol[x[1]].push_back(x[0]);
ver.add(x[0], x[1]);
//~ cout<<x[0]<<" "<<x[1]<<"\n";
auto t = x; t[0]++, t[1]++;
row[x[0]].push_back(x[1]);
col[x[1]].push_back(x[0]);
}
ed[0].build();
ed[1].build();
ver.build();
sq.build();
for(int i=0;i<N;i++){
sort(row[i].begin(), row[i].end());
sort(col[i].begin(), col[i].end());
sort(erow[i].begin(), erow[i].end());
sort(ecol[i].begin(), ecol[i].end());
}
}
/*
6 4 9 4
3 3
NWESSWEWS
2 3 2 3
3 2 4 4
5 3 6 4
1 2 5 3
*/
ar<int, 2> get_r(int x, int l, int r){
auto R = upper_bound(row[x].begin(), row[x].end(), r);
auto L = lower_bound(row[x].begin(), row[x].end(), l);
int v = R - L;
r--;
R = upper_bound(erow[x].begin(), erow[x].end(), r);
L = lower_bound(erow[x].begin(), erow[x].end(), l);
int e = R - L;
return {v, e};
}
ar<int, 2> get_l(int x, int l, int r){
auto R = upper_bound(col[x].begin(), col[x].end(), r);
auto L = lower_bound(col[x].begin(), col[x].end(), l);
int v = R - L;
r--;
R = upper_bound(ecol[x].begin(), ecol[x].end(), r);
L = lower_bound(ecol[x].begin(), ecol[x].end(), l);
int e = R - L;
return {v, e};
}
int colour(int lx, int ly, int rx, int ry) {
int ee = ed[0].get(lx, rx + 1, ly, ry);
ee += ed[1].get(lx, rx, ly, ry + 1);
int V = ver.get(lx, rx + 1, ly, ry + 1);
auto t = get_r(lx, ly, ry + 1);
//~ cout<<V<<" "<<ee<<endl;
V += (ry - ly + 2 - t[0]);
ee += (ry - ly + 1 - t[1]);
t = get_r(rx + 1, ly, ry + 1);
V += (ry - ly + 2 - t[0]);
ee += (ry - ly + 1 - t[1]);
t = get_l(ly, lx, rx + 1);
V += (rx - lx + 2 - t[0]);
ee += (rx - lx + 1 - t[1]);
t = get_l(ry + 1, lx, rx + 1);
V += (rx - lx + 2 - t[0]);
ee += (rx - lx + 1 - t[1]);
if(!tot.count({lx, ly})) V--;
if(!tot.count({lx, ry + 1})) V--;
if(!tot.count({rx + 1, ly})) V--;
if(!tot.count({rx + 1, ry + 1})) V--;
int F = sq.get(lx, rx, ly, ry);
//~ cout<<V<<" "<<ee<<" "<<F<<"\n";
return (2 - V + ee - F - 1);
}
