#include "rainbow.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define int long long
#define i32 int32_t
#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){
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;
set<ar<int, 2>> ss, tot, is[2];
int Lx, Rx, Ly, Ry;
void init(i32 n, i32 m, i32 x, i32 y, i32 k, char *s) {
ss.insert({x, y});
Lx = Rx = x, Ly = Ry = 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});
Lx = min(Lx, 1ll * x);
Rx = max(Rx, 1ll * x);
Ly = min(Ly, 1ll * y);
Ry = max(Ry, 1ll * 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]);
if(is[1].count(x)) ed[1].add(x[0], x[1]);
ver.add(x[0], x[1]);
}
ed[0].build();
ed[1].build();
ver.build();
sq.build();
}
/*
6 4 9 4
3 3
NWESSWEWS
2 3 2 3
3 2 4 4
5 3 6 4
1 2 5 3
13 13 13 1
6 8
WWWEENWEEWEWE
3 4 10 13
13 13 26 1
5 9
SEWSWEENSNSNSEENSNSNNNWWSN
1 5 8 13
*/
i32 colour(i32 lx, i32 ly, i32 rx, i32 ry) {
if(lx > rx) swap(lx, rx);
if(ly > ry) swap(ly, 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);
int tmp = 0, tt = 0;
tmp += ver.get(lx, lx, ly, ry + 1);
tt += ed[0].get(lx, lx, ly, ry);
tmp += ver.get(rx + 1, rx + 1, ly, ry + 1);
tt += ed[0].get(rx + 1, rx + 1, ly, ry);
if(lx < rx) tmp += ver.get(lx + 1, rx, ly, ly);
tt += ed[1].get(lx, rx, ly, ly);
if(lx < rx) tmp += ver.get(lx + 1, rx, ry + 1, ry + 1);
tt += ed[1].get(lx, rx, ry + 1, ry + 1);
int v = (rx - lx + ry - ly + 2) * 2;
V += (v - tmp);
ee += (v - tt);
//~ cout<<tmp<<" "<<tt<<"\n";
int F = sq.get(lx, rx, ly, ry);
//~ assert(1 - V + ee - F >= 0);
int res = (1 - V + ee - F);
if(lx < Lx && Rx < rx && ly < Ly && Ry < ry){
res++;
}
return res;
}
