#define DEBUG 0
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
const int INF=0x3f3f3f3f;
const int N=2e5+5;
const int OFF=(1<<18);
int uk=1;
int lef[150*N], rig[150*N], val[150*N];
vector <int> v_br[N], v_v[N], v_ok[N], v_vod[N];
int novi(int x, int l, int r) {
lef[uk]=l; rig[uk]=r;
val[uk]=x;
return uk++;
}
int upd(int ind, int pos, int lo, int hi) {
if (ind>=hi || ind<lo) return pos;
if (lo==hi-1) return novi(1+val[pos], 0, 0);
int mid=(lo+hi)/2;
return novi(1+val[pos], upd(ind, lef[pos], lo, mid), upd(ind, rig[pos], mid, hi));
}
int que(int a, int b, int pos, int lo, int hi) {
if (!pos) return 0;
if (lo>=b || hi<=a) return 0;
if (lo>=a && hi<=b) return val[pos];
int mid=(lo+hi)/2;
return que(a, b, lef[pos], lo, mid)+que(a, b, rig[pos], mid, hi);
}
struct Tour{
int T[N];
Tour() {
memset(T, 0, sizeof T);
}
int& operator [] (int x) {
return T[x];
}
void update(int r, int c) {
if (T[r]==0) T[r]=T[r-1];
T[r]=upd(c, T[r], 0, OFF);
}
int query(int r1, int c1, int r2, int c2) {
return que(c1, c2+1, T[r2], 0, OFF)-que(c1, c2+1, T[r1-1], 0, OFF);
}
};
int mxr, mnr, mxc, mnc;
void dodaj(int r, int c) {
v_br[r].pb(c);
v_v[r].pb(c); v_v[r].pb(c+1);
v_v[r+1].pb(c); v_v[r+1].pb(c+1);
v_ok[r].pb(c); v_ok[r].pb(c+1);
v_vod[r].pb(c); v_vod[r+1].pb(c);
mxr=max(mxr, r); mxc=max(mxc, c);
mnr=min(mnr, r); mnc=min(mnc, c);
}
void sazmi(vector <int> &v) {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
}
Tour Tvod, Tok, Tv, Tbr;
void init(int R, int C, int sr, int sc, int M, char *S) {
mxr=mnr=sr; mxc=mnc=sc;
dodaj(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++;
dodaj(sr, sc);
}
for (int i=1; i<=R; ++i) {
sazmi(v_br[i]); sazmi(v_v[i]); sazmi(v_ok[i]); sazmi(v_vod[i]);
for (int x:v_br[i]) Tbr.update(i, x);
for (int x:v_v[i]) Tv.update(i, x);
for (int x:v_ok[i]) Tok.update(i, x);
for (int x:v_vod[i]) Tvod.update(i, x);
}
}
int colour(int r1, int c1, int r2, int c2) {
int red=r2-r1+1, col=c2-c1+1;
int v=Tv.query(r1+1, c1+1, r2, c2)+2*(red+col);
int e=Tok.query(r1, c1+1, r2, c2)+Tvod.query(r1+1, c1, r2, c2)+2*(red+col);
int comp=1;
if (r1<mnr && r2>mxr && c1<mnc && c2>mxc) ++comp;
int f=1-v+e+comp;
int br=Tbr.query(r1, c1, r2, c2);
#if DEBUG
printf("v: %d, e: %d, comp: %d\nf: %d, br: %d\n", v, e, comp, f, br);
#endif // DEBUG
return f-br-1;
}
