#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define info() cerr << __PRETTY_FUNCTION__ << ": " << __LINE__ << endl
void abc() {cerr << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cerr << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << '(' << a.X << ", " << a.Y << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
return o << '}';
}
template <typename T> struct vv : vector <vector <T>> {
vv(int n, int m, int v = 0) : vector <vector <T>> (n, vector <T>(m, v)) {}
vv() {}
};
template <typename T> struct vvv : vector <vv <T>> {
vvv(int n, int m, int k, int v = 0) : vector <vv <T>> (n, vv <T>(m, k, v)) {}
vvv() {}
};
#ifdef Doludu
#define test(args...) info(), abc("[" + string(#args) + "]", args)
#define owo
#include "rainbow-grader.cpp"
#else
#define test(args...)
#define owo ios::sync_with_stdio(false); cin.tie(0)
#endif
const int mod = 998244353, N = 200001, logN = 20, K = 111, NN = 4e7;
struct Seg {
static Seg mem[NN], *pt;
int l, r, m, sum;
Seg* ch[2];
Seg () = default;
Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1) {
if (r - l > 1) {
ch[0] = new (pt++) Seg(l, m);
ch[1] = new (pt++) Seg(m, r);
} else {
sum = 0;
}
}
Seg* modify(int p) {
Seg *now = new (pt++) Seg(*this);
now->sum++;
if (r - l == 1) return now;
else now->ch[p >= m] = now->ch[p >= m]->modify(p);
return now;
}
int query(int a, int b) {
if (a >= b) return 0;
if (a <= l && r <= b) return sum;
int ans = 0;
if (a < m) ans += ch[0]->query(a, b);
if (m < b) ans += ch[1]->query(a, b);
return ans;
}
} Seg::mem[NN], *Seg::pt = mem;
vector <Seg*> vertex, seg_row, seg_col, cell;
int mn_r = N, mx_r = 0, mn_c = N, mx_c = 0;
void init(int n, int m, int r, int c, int k, char *s) {
r--, c--;
vertex.pb(new (Seg::pt++) Seg(0, m + 1));
seg_row.pb(new (Seg::pt++) Seg(0, m));
seg_col.pb(new (Seg::pt++) Seg(0, m + 1));
cell.pb(new Seg(0, m));
vector <int> v[n + 1], sr[n + 1], sc[n], cc[n];
auto add = [&](int r, int c) {
v[r].pb(c);
v[r].pb(c + 1);
v[r + 1].pb(c);
v[r + 1].pb(c + 1);
sr[r].pb(c);
sr[r + 1].pb(c);
sc[r].pb(c);
sc[r].pb(c + 1);
cc[r].pb(c);
mn_r = min(mn_r, r);
mx_r = max(mx_r, r);
mn_c = min(mn_c, c);
mx_c = max(mx_c, c);
};
add(r, c);
for (int i = 0; i < k; ++i) {
if (s[i] == 'W') c--;
if (s[i] == 'E') c++;
if (s[i] == 'N') r--;
if (s[i] == 'S') r++;
add(r, c);
}
{
for (int i = 0; i < n + 1; ++i) {
sort(all(v[i]));
v[i].resize(unique(all(v[i])) - v[i].begin());
Seg* now = vertex.back();
for (int j : v[i]) {
now = now->modify(j);
}
vertex.pb(now);
}
}
{
for (int i = 0; i < n + 1; ++i) {
sort(all(sr[i]));
sr[i].resize(unique(all(sr[i])) - sr[i].begin());
Seg* now = seg_row.back();
for (int j : sr[i]) {
now = now->modify(j);
}
seg_row.pb(now);
}
}
{
for (int i = 0; i < n; ++i) {
sort(all(sc[i]));
sc[i].resize(unique(all(sc[i])) - sc[i].begin());
Seg* now = seg_col.back();
for (int j : sc[i]) {
now = now->modify(j);
}
seg_col.pb(now);
}
}
{
for (int i = 0; i < n; ++i) {
sort(all(cc[i]));
cc[i].resize(unique(all(cc[i])) - cc[i].begin());
Seg* now = cell.back();
for (int j : cc[i]) {
now = now->modify(j);
}
cell.pb(now);
}
}
}
int colour(int l1, int r1, int l2, int r2) {
l1--, r1--;
// F = E - V + 1 + C
// ans = E - V + C - A, A -> cell
int V = vertex[l2]->query(r1 + 1, r2) - vertex[l1 + 1]->query(r1 + 1, r2) + (l2 - l1 + 1) * 2 + (r2 - r1 + 1) * 2 - 4;
int E1 = seg_row[l2]->query(r1, r2) - seg_row[l1 + 1]->query(r1, r2) + (r2 - r1) * 2;
int E2 = seg_col[l2]->query(r1 + 1, r2) - seg_col[l1]->query(r1 + 1, r2) + (l2 - l1) * 2;
int C = (l1 < mn_r && mx_r + 1 < l2 && r1 < mn_c && mx_c +1 < r2 ? 2 : 1);
int A = cell[l2]->query(r1, r2) - cell[l1]->query(r1, r2);
return E1 + E2 - V + C - A;
}
/*
6 4 9 4
3 3
NWESSWEWS
2 3 2 3
3 2 4 4
5 3 6 4
1 2 5 3
*/
