#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
#define mp make_pair
#define f first
#define s second
#define ins insert
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
void ckmin(int& a, int b){
a = min(a, b);
}
void ckmax(int& a, int b){
a = max(a, b);
}
vector<char> dchar = vector<char>{'S', 'E', 'N', 'W'};
vi dx = vi{1, 0, -1, 0};
vi dy = vi{0, 1, 0, -1};
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
struct hashFunc{
size_t operator()(pi a) const {
ll res = ll(a.f)*200005+ll(a.s);
ll BIG_RAND = 102923014203249LL;
return __builtin_bswap64((unsigned long long)(res)*BIG_RAND);
}
};
const int mx = 200005;
struct Off2DBIT{
ll bt[mx*20];
vi all_ys;
int begin_index[mx];
int num[mx];
vpi all_updates;
void update(int X, int Y){
all_updates.pb(mp(X, Y));
}
void UPD(int X, int Y){
for(int i = X; i < mx; i+=i&-i){
int pos = lower_bound(begin(all_ys)+begin_index[i], begin(all_ys)+begin_index[i]+num[i], Y)-begin(all_ys)-begin_index[i]+1;
for(int j = pos; j <= num[i]; j+=j&-j){
bt[begin_index[i]-1+j]++;
}
}
}
vi to_add_ys[mx];
int last_num[mx];
void initBT(){
// cout << "all_updates: " << "\n";
// for(const auto& u: all_updates){
// cout << u.f << " " << u.s << "\n";
// }
for(auto &u: all_updates){
swap(u.s, u.f);
}
sort(all(all_updates));
for(const auto& u: all_updates){
for(int i = u.s; i < mx; i+=i&-i){
if(last_num[i] != u.f){
last_num[i] = u.f;
to_add_ys[i].pb(u.f);
}
}
}
int cur = 0;
for(int i = 1; i < mx; i++){
begin_index[i] = cur;
num[i] = sz(to_add_ys[i]);
for(const auto& u: to_add_ys[i]){
all_ys.pb(u);
}
vi v;
swap(to_add_ys[i], v);
cur+=num[i];
}
for(auto &u: all_updates){
swap(u.s, u.f);
}
for(const auto& u: all_updates){
UPD(u.f, u.s);
}
// cout << "all_ys: ";
// for(auto u: all_ys){
// cout << u << " ";
// }
// cout << "\n";
// for(int i = 1; i < 5; i++){
// cout << i << " " << begin_index[i] << " " << num[i] << "\n";
// }
// cout << "\n";
}
ll sum(int x_coor, int y_coor){
ll res = 0;
for(int i = x_coor; i > 0; i-=i&-i){
int pos = upper_bound(begin(all_ys)+begin_index[i], begin(all_ys)+begin_index[i]+num[i], y_coor)-begin(all_ys)-begin_index[i];
for(int j = pos; j > 0; j-=j&-j){
res+=bt[begin_index[i]-1+j];
}
}
// cout << "sum(" << x_coor << ", " << y_coor << "): " << res << "\n";
return res;
}
ll query(int xl, int yl, int xr, int yr){
return sum(xr, yr)-sum(xl-1, yr)-sum(xr, yl-1)+sum(xl-1, yl-1);
}
// ll query(int xl, int yl, int xr, int yr){
// ll res = 0;
// for(auto& u: all_updates){
// if(xl <= u.f && u.f <= xr && yl <= u.s && u.s <= yr){
// res++;
// }
// }
// return res;
// }
};
Off2DBIT bits[2][2];
gp_hash_table<pi, null_type, hashFunc> rects[4];
int min_sr, max_sr, min_sc, max_sc;
void init(int R, int C, int sr, int sc, int M, char *S) {
min_sr = sr;
min_sc = sc;
max_sr = sr;
max_sc = sc;
for(int i = 0; i <= M; i++){
for(int i = 0; i <= 1; i++){
for(int j = 0; j <= 1; j++){
for(int xl = sr-i; xl <= sr; xl++){
for(int yl = sc-j; yl <= sc; yl++){
if(1 <= xl && 1 <= yl){
rects[2*i+j][mp(xl, yl)];
}
}
}
}
}
if(i < M){
for(int d = 0; d < 4; d++){
if(S[i] == dchar[d]){
sr+=dx[d];
sc+=dy[d];
break;
}
}
}
ckmin(min_sr, sr);
ckmin(min_sc, sc);
ckmax(max_sr, sr);
ckmax(max_sc, sc);
}
for(int i = 0; i <= 1; i++){
for(int j = 0; j <= 1; j++){
// cout << "i, j = " << i << ", " << j << "\n";
for(auto u: rects[2*i+j]){
// cout << "RECT " << i << " " << j << " " << u.f << " " << u.s << "\n";
bits[i][j].update(u.f, u.s);
}
}
}
for(int i = 0; i <= 1; i++){
for(int j = 0; j <= 1; j++){
bits[i][j].initBT();
}
}
}
int colour(int ar, int ac, int br, int bc) {
ll ans = 0;
if(ar+1 <= min_sr && max_sr+1 <= br && ac+1 <= min_sc && max_sc+1 <= bc){
ans++;
}
for(int i = 0; i <= 1; i++){
for(int j = 0; j <= 1; j++){
ll val = ll(br-i-ar+1)*ll(bc-j-ac+1);
// cout << "val: " << val << "\n";
// cout << "querying " << i << " " << j << "\n";
val-=bits[i][j].query(ar, ac, br-i, bc-j);
if((i+j) % 2 == 0){
ans+=val;
}
else{
ans-=val;
}
// cout << i << " " << j << " " << val << "\n";
}
}
return (int)(ans);
}
