#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define unicorn(x) x.resize(unique(all(x))-x.begin())
typedef pair<int,int> pii;
#define f first
#define s second
string pr(vector<pii> vv){for(auto [x,y]:vv)cout<<"("<<x<<","<<y<<") ";return"";}
string pr(vector<int> vv){for(auto i:vv)cout<<i<<" ";return"";}
const int L=2e5+10, inf=1e9+10;
int MA;
int xmx=-inf, xmn=inf, ymx=-inf, ymn=inf;
vector<pii> P;
struct RC{
struct node{
int l,r,mid,sum;
node* lc;
node* rc;
node(int l2, int r2){
l = l2;
r = r2;
lc = nullptr;
rc = nullptr;
mid = (l+r)/2;
sum = 0;
}
void spread(){
if(lc == nullptr){
lc = new node(l,mid);
rc = new node(mid,r);
}
}
void update(int ind,int x,node* newnode){
if(l+1 == r){
newnode->sum = sum;
newnode->sum += x;
return;
}
spread();
if(ind < mid){
newnode->rc = rc;
newnode->lc = new node(l,mid);
lc->update(ind,x,newnode->lc);
}
else{
newnode->lc = lc;
newnode->rc = new node(mid,r);
rc->update(ind,x,newnode->rc);
}
newnode->sum = newnode->lc->sum + newnode->rc->sum;
}
int get(int l2,int r2){
if(l==l2 and r==r2)
return sum;
int ans = 0;
spread();
if(l2 < mid)
ans += lc->get(l2,min(r2,mid));
if(r2 > mid)
ans += rc->get(max(l2,mid),r2);
return ans;
}
};
node* R[L];
vector<int> good[L];
void add(int x,int y){
good[x].pb(y);
}
void build(){
R[L-1] = new node(1,L);
for(int i=L-2;i>=1;i--){
R[i] = R[i+1];
sort(all(good[i]));
unicorn(good[i]);
for(auto x:good[i]){
node* rt = new node(1,L);
R[i]->update(x,1,rt);
R[i] = rt;
}
}
}
int get(int x,int y){
return R[x]->get(y,L);
}
}oo,ot,to,tt;
void init(int A,int B,int sx,int sy,int N,char* S){
P.pb(pii(sx,sy));
for(auto c:S){
if(c == 'N')
sx--;
if(c == 'S')
sx++;
if(c == 'W')
sy--;
if(c == 'E')
sy++;
P.pb(pii(sx,sy));
}
sort(all(P));
unicorn(P);
map<pii,bool> is;
for(auto [x,y]:P){
//oo
oo.add(x,y);
//ot
ot.add(x,y);
ot.add(x-1,y);
//to
to.add(x,y);
to.add(x,y-1);
//tt
tt.add(x,y);
tt.add(x-1,y);
tt.add(x,y-1);
tt.add(x-1,y-1);
is[pii(x,y)] = 1;
xmx = max(xmx , x);
ymn = max(ymx , y);
xmn = max(xmn , x);
ymn = max(ymn , y);
}
oo.build();
ot.build();
to.build();
tt.build();
if(xmx!=A and xmn!=1 and ymx!=B and ymn!=1){
MA = 0;
for(auto [x,y]:P){
MA += is[pii(x+1,y)];
MA += is[pii(x,y+1)];
MA += is[pii(x-1,y)];
MA += is[pii(x,y-1)];
}
MA /= 2;
MA = MA - P.size() + 2;
for(auto [x,y]:P){
MA -= (is[pii(x+1,y)] and is[pii(x,y+1)] and is[pii(x+1,y+1)]);
}
}
cout<<"P: "<<pr(P)<<endl;
for(int i=1;i<=4;i++){
cout<<"good["<<i<<"]: "<<pr(to.good[i])<<endl;
}
}
ll get(int x1,int y1,int x2,int y2, RC &X){
if(x2 <= x1 or y2 <= y1)
return 0;
ll ans = (x2-x1)*(y2-y1);
ans -= X.get(x1,y1);
ans -= X.get(x2,y2);
ans += X.get(x1,y2);
ans += X.get(x2,y1);
return ans;
}
int colours(int x1,int y1,int x2,int y2){
if(x1<xmn and x2>xmx and y1<ymn and y2>ymx)
return MA;
x2++;
y2++;
return get(x1,y1,x2,y2,oo) - get(x1,y1,x2-1,y2,ot) - get(x1,y1,x2,y2-1,to) + get(x1,y1,x2-1,y2-1,tt);
}
/*
int main(){
ifstream cin ("in.in");
int X,Y,sx,sy,N,q;
string I;
cin>>X>>Y>>N>>q;
cin>>sx>>sy;
cin>>I;
init(X,Y,sx,sy,N,I);
for(int i=1;i<=q;i++){
int x1,x2,y1,y2;
cin >> x1 >> y1 >> x2 >> y2;
cout<<i<<" --> "<<colours(x1,y1,x2,y2)<<endl;
}
}
*/
