#include "rainbow.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define all(m) (m).begin(), (m).end()
#define rall(m) (m).rbegin(), (m).rend()
#define vec vector
#define sz(a) (int) (a).size()
#define mpp make_pair
#define mtt make_tuple
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
typedef tuple <int, int, int> tui;
template <typename T>
using prq = priority_queue <T>;
template <typename T>
using pgq = priority_queue <T, vec <T>, greater <T>>;
template <typename T> bool umin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> bool umax(T &a, T b) { return a < b ? a = b, 1 : 0; }
typedef struct node* pnode;
struct node{
int s;
pnode l, r;
node(int x = 0): s(x) { l = r = nullptr; }
node(pnode tl, pnode tr): l(tl), r(tr) {
s = 0;
if (l) s += l->s;
if (r) s += r->s;
}
};
pnode build(int tl, int tr){
if (tl + 1 == tr) return new node();
int tm = tl + tr >> 1;
return new node(build(tl, tm), build(tm, tr));
}
pnode upd(int p, int x, int tl, int tr, pnode t){
if (tl + 1 == tr) return new node(t->s + x);
int tm = tl + tr >> 1;
if (p < tm) return new node(upd(p, x, tl, tm, t->l), t->r);
return new node(t->l, upd(p, x, tm, tr, t->r));
}
int get(int l, int r, int tl, int tr, pnode t){
if (!t || l >= r) return 0;
if (tl == l && tr == r) return t->s;
int tm = tl + tr >> 1;
return get(l, min(tm, r), tl, tm, t->l)
+ get(max(l, tm), r, tm, tr, t->r);
}
struct sum2d{
int n, m;
vec <pnode> t;
vec <map <int, int>> updates;
sum2d() {}
sum2d(int n, int m): n(n), m(m) {
t.resize(n);
updates.resize(n);
}
void mark(int x, int y){
assert(x < n);
assert(x >= 0);
assert(y < m);
assert(y >= 0);
updates[x][y] = 1;
}
void init(){
t[0] = build(0, m);
for (int i = 0; i < n; ++i){
if (i) t[i] = t[i - 1];
for (auto &[y, d]: updates[i]){
t[i] = upd(y, d, 0, m, t[i]);
}
}
}
int sum(int lx, int ly, int rx, int ry){ // sum on [lx, rx] U [ly, ry]
int ans = get(ly, ry + 1, 0, m, t[rx]);
if (lx) ans -= get(ly, ry + 1, 0, m, t[lx - 1]);
return ans;
}
int at(int x, int y){
int ans = get(y, y + 1, 0, m, t[x]);
if (x) ans -= get(y, y + 1, 0, m, t[x - 1]);
return ans;
}
};
sum2d f, v_e, h_e, v;
void init(int R, int C, int sr, int sc, int M, char *S) {
--sr, --sc;
f = sum2d(R, C);
v_e = sum2d(R, C + 1);
h_e = sum2d(R + 1, C);
v = sum2d(R + 1, C + 1);
auto mark = [&](int x, int y){
f.mark(x, y);
v.mark(x, y);
v.mark(x + 1, y);
v.mark(x, y + 1);
v.mark(x + 1, y + 1);
h_e.mark(x, y);
h_e.mark(x + 1, y);
v_e.mark(x, y);
v_e.mark(x, y + 1);
};
mark(sr, sc);
for (int i = 0; i < M; ++i){
if (S[i] == 'N') --sr;
if (S[i] == 'S') ++sr;
if (S[i] == 'W') --sc;
if (S[i] == 'E') ++sc;
mark(sr, sc);
}
f.init();
v.init();
h_e.init();
v_e.init();
// cout << "\n";
// for (int i = 0; i < R; ++i){
// for (int j = 0; j < C; ++j){
// cout << f.at(i, j);
// }
// cout << "\n";
// }
// cout << "\n";
}
int colour(int lx, int ly, int rx, int ry) {
--lx, --ly, --rx, --ry;
int extra_faces = f.sum(lx, ly, rx, ry); // river cells
int vertices = v.sum(lx, ly, rx + 1, ry + 1); // inside
vertices += rx - lx + 2 - v.sum(lx, ly, rx + 1, ly);
vertices += rx - lx + 2 - v.sum(lx, ry + 1, rx + 1, ry + 1);
vertices += ry - ly - v.sum(lx, ly + 1, lx, ry);
vertices += ry - ly - v.sum(rx + 1, ly + 1, rx + 1, ry); // borders
// cout << "inside: " << v.sum(lx, ly, rx + 1, ry + 1) << "\n";
// cout << "left border: " << rx - lx + 2 << " - " << v.sum(lx, ly, rx + 1, ly) << "\n";
// cout << "right border: " << rx - lx + 2 << " - " << v.sum(lx, ry + 1, rx + 1, ry + 1) << "\n";
// cout << "top border: " << ry - ly << " - " << v.sum(lx, ly + 1, lx, ry) << "\n";
// cout << "bottom border: " << ry - ly << " - " << v.sum(rx + 1, ly + 1, rx + 1, ry) << "\n";
// cout << "\n";
int v_edges = v_e.sum(lx, ly, rx, ry + 1); // inside
v_edges += rx - lx + 1 - v_e.sum(lx, ly, rx, ly);
v_edges += rx - lx + 1 - v_e.sum(lx, ry + 1, rx, ry + 1); // borders
int h_edges = h_e.sum(lx, ly, rx + 1, ry); //inside
h_edges += ry - ly + 1 - h_e.sum(lx, ly, lx, ry);
h_edges += ry - ly + 1 - h_e.sum(rx + 1, ly, rx + 1, ry); // borders
// cout << "hor inside: " << h_e.sum(lx, ly, rx + 1, ry) << "\n";
// cout << "hor top border: " << ry - ly + 1 << " - " << h_e.sum(lx, ly, lx, ry) << "\n";
// cout << "hor bottom border: " << ry - ly + 1 << " - " << h_e.sum(rx + 1, ly, rx + 1, ry) << "\n";
// cout << "\n";
//
// cout << "v_e:" << v_edges << "\n";
// cout << "h_e:" << h_edges << "\n";
// cout << "v:" << vertices << "\n";
// cout << "e_f:" << extra_faces << "\n";
return 2 + v_edges + h_edges - vertices - extra_faces - 1; //using v - e + f = 2 => f = 2 + e - v
}
