#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
#define all(x) x.begin(),x.end()
#define COMP(x) x.erase(unique(all(x)),x.end())
#define sz(x) x.size()
vector<pi> white_grid; //흰색(강) 그리드 위치 관리
vector<int> white[202020];
ll n, m;
struct PST{
struct Node{
int l,r,v;
Node(): l(-1), r(-1), v(0){}
};
int M=0;
vector<Node> tree; vector<int> root;
//트리 1개에 O(C), 업데이트가 O(M)개 있다고 생각하면 O(C+ClogM) 대충 200000*21*4 900만개 정도. 2~4배 정도 뛸수 있음
void init(int node, int s, int e){
if(s==e)return;
ll mid = s+e>>1;
tree[node].l = ++M;
tree[node].r = ++M;
init(tree[node].l,s,mid); init(tree[node].r,mid+1,e);
}
void upd_tree(int cur, int prv, int s, int e, int i, int d){ //i에 d를 더하기
if(s==e){
tree[cur].v = (prv<0?0:tree[prv].v)+d;
return;
}
}
int query(int node, int s, int e, int l, int r){
if(node<0 or e<l or r<s)return 0;
if(l<=s and e<=r)return tree[node].v;
ll mid = s+e>>1; return query(tree[node].l,s,mid,l,r) + query(tree[node].r,mid+1,e,l,r);
}
int sum(int x1, int y1, int x2, int y2){
return query(root[x2],1,m,y1,y2) - query(root[x1-1],1,m,y1,y2);
}
ll single_sum(int x1, int y1){ if(x1<=0 or y1<=0)return 0; return (ll)x1*y1 - query(root[x1],1,m,1,y1); }
ll single_sum2(int x1, int y1){ if(x1<=0 or y1<=0)return 0; return (ll)(x1-1)*(y1-1) - query(root[x1],1,m,1,y1); } //Black
ll single_sum3(int x1, int y1){ if(x1<=0 or y1<=0)return 0; return (ll)x1*y1 - query(root[x1],1,m,1,y1); } //Down
ll single_sum4(int x1, int y1){ if(x1<=0 or y1<=0)return 0; return (ll)x1*y1 - query(root[x1],1,m,1,y1); } //Right
int rev_single_sum(int x1, int y1){ if(x1<=0 or y1<=0)return 0; return query(root[x1],1,m,1,y1); }
}W,B,R,D;
void init(int RR, int CC, int r, int c, int M, char *S) {
n=RR,m=CC;
white_grid.push_back({r,c});
for(int i = 0 ; i < M ; i++){
if(S[i]=='N')r--;
if(S[i]=='S')r++;
if(S[i]=='E')c++;
if(S[i]=='W')c--;
white_grid.push_back({r,c});
}
sort(all(white_grid)); COMP(white_grid);
for(auto [i,j] : white_grid)white[i].push_back(j);
W.tree.resize(9000000); W.root.resize(n+1); W.init(1,1,m);
B.tree.resize(9000000); B.root.resize(n+1); B.init(1,1,m);
R.tree.resize(9000000); R.root.resize(n+1); R.init(1,1,m);
D.tree.resize(9000000); D.root.resize(n+1); D.init(1,1,m);
//White : (i,j)가 white일 때 1
ll prv_root = 0;
for(int i = 1 ; i <= n ; i++){
ll prv_root = W.root[i-1];
for(auto j : white[i]){
ll cur = ++W.M;
W.upd_tree(cur,prv_root,1,m,j,1);
prv_root = cur;
}
W.root[i] = prv_root;
}
}
int colour(int x1, int y1, int x2, int y2) {
return 0;
}
