#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define SZ(x) int((x).size())
#define sep ' '
#define endl '\n'
#define lc id << 1
#define rc lc | 1
const int MAXN = 2e5 + 10;
const int LOG = 22;
const int MOD = 1e9 + 7;
const ll INF = 2e18;
int mnx = MOD , mny = MOD , mxx = 0 , mxy = 0;
vector<pii> points , ptr[4][MAXN << 2];
vector<int> vec[4][MAXN] , seg[4][MAXN << 2];
void merge(int ind , int id){
int ptr1 = 0 , ptr2 = 0;
while(ptr1 < SZ(seg[ind][lc]) && ptr2 < SZ(seg[ind][rc])){
ptr[ind][id].push_back({ptr1 , ptr2});
if(seg[ind][lc][ptr1] < seg[ind][rc][ptr2]){
seg[ind][id].push_back(seg[ind][lc][ptr1++]);
}
else{
seg[ind][id].push_back(seg[ind][rc][ptr2++]);
}
}
while(ptr1 < SZ(seg[ind][lc])){
ptr[ind][id].push_back({ptr1 , ptr2});
seg[ind][id].push_back(seg[ind][lc][ptr1++]);
}
while(ptr2 < SZ(seg[ind][rc])){
ptr[ind][id].push_back({ptr1 , ptr2});
seg[ind][id].push_back(seg[ind][rc][ptr2++]);
}
ptr[ind][id].push_back({ptr1 , ptr2});
}
void build(int ind , int id = 1 , int l = 0 , int r = MAXN){
if(r - l == 1){
seg[ind][id] = vec[ind][l];
sort(all(seg[ind][id]));
seg[ind][id].resize(unique(all(seg[ind][id])) - seg[ind][id].begin());
return;
}
int mid = l + r >> 1;
build(ind , lc , l , mid);
build(ind , rc , mid , r);
merge(ind , id);
}
int get(int ind , int ql , int qr , int x , int bs = -1 , int id = 1 , int l = 0 , int r = MAXN){
if(bs == -1) bs = lower_bound(all(seg[ind][id]) , x) - seg[ind][id].begin();
if(qr <= l || r <= ql) return 0;
if(ql <= l && r <= qr) return bs;
int mid = l + r >> 1;
return get(ind , ql , qr , x , ptr[ind][id][bs].X , lc , l , mid) + get(ind , ql , qr , x , ptr[ind][id][bs].Y , rc , mid , r);
}
void init(int n, int m, int sr, int sc, int M, char *S) {
points.push_back({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++;
points.push_back({sr , sc});
}
for(pii i : points){
int x = i.X , y = i.Y;
// cout << x << sep << y << endl;
mnx = min(mnx , x); mxx = max(mxx , x);
mny = min(mny , y); mxy = max(mxy , y);
vec[0][x].push_back(y);
vec[1][x].push_back(y); vec[1][x].push_back(y - 1);
vec[2][x].push_back(y); vec[2][x - 1].push_back(y);
vec[3][x].push_back(y); vec[3][x].push_back(y - 1);
vec[3][x - 1].push_back(y); vec[3][x - 1].push_back(y - 1);
}
build(0); build(1); build(2); build(3);
}
int colour(int ar, int ac, int br, int bc) {
ll ans = (mnx > ar && br > mxx && mny > ac && bc > mxy) , R = br - ar + 1 , C = bc - ac + 1;
br++; bc++;
ans += R * C - (get(0 , ar , br , bc) - get(0 , ar , br , ac));
ans -= R * (C - 1) - (get(1 , ar , br , bc - 1) - get(1 , ar , br , ac));
ans -= (R - 1) * C - (get(2 , ar , br - 1 , bc) - get(2 , ar , br - 1 , ac));
ans += (R - 1) * (C - 1) - (get(3 , ar , br - 1 , bc - 1) - get(3 , ar , br - 1 , ac));
// cout << mnx << sep << mxx << sep << mny << sep << mxy << endl;
return ans;
}
