#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 mid = s+e>>1;
if(i<=mid){
//L은 새로 만들고 R은 그대로
tree[cur].l = ++M;
tree[cur].r = tree[prv].r;
upd_tree(tree[cur].l,tree[prv].l,s,mid,i,d);
}
else{
tree[cur].r = ++M;
tree[cur].l = tree[prv].l;
upd_tree(tree[cur].r,tree[prv].r,mid+1,e,i,d);
}
tree[cur].v = (tree[cur].l>=0?tree[tree[cur].l].v:0) + (tree[cur].r>=0?tree[tree[cur].r].v:0);
}
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(0,1,m);
B.tree.resize(9000000); B.root.resize(n+1); B.init(0,1,m);
R.tree.resize(9000000); R.root.resize(n+1); R.init(0,1,m);
D.tree.resize(9000000); D.root.resize(n+1); D.init(0,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;
}
//Black : (i,j), (i,j-1), (i-1,j), (i-1,j-1)중 하나라도 white일 때 1
for(int i = 1 ; i <= n ; i++)white[i].clear();
for(auto [i,j] : white_grid){
vector<pi> v = {{0,0},{0,1},{1,0},{1,1}};
for(auto [di,dj] : v){
int ni = i+di, nj = j+dj;
if(ni<1 or nj<1 or ni>n or nj>m)continue;
white[ni].push_back(nj);
}
}
prv_root = 0;
for(int i = 1 ; i <= n ; i++){
ll prv_root = B.root[i-1];
sort(all(white[i])); COMP(white[i]);
for(auto j : white[i]){
ll cur = ++B.M;
B.upd_tree(cur,prv_root,1,m,j,1);
prv_root = cur;
}
B.root[i] = prv_root;
}
//Right : (i,j)와 (i,j+1) 중 하나라도 white일 때 1
for(int i = 1 ; i <= n ; i++)white[i].clear();
for(auto [i,j] : white_grid){
for(int k = -1 ; k <= 0 ; k++){
int ni = i, nj = j+k;
if(nj<1 or nj>m)continue;
white[ni].push_back(nj);
}
}
prv_root = 0;
for(int i = 1 ; i <= n ; i++){
ll prv_root = R.root[i-1];
sort(all(white[i])); COMP(white[i]);
for(auto j : white[i]){
ll cur = ++R.M;
R.upd_tree(cur,prv_root,1,m,j,1);
prv_root = cur;
}
R.root[i] = prv_root;
}
//Down : (i,j)와 (i+1,j)
for(int i = 1 ; i <= n ; i++)white[i].clear();
for(auto [i,j] : white_grid){
for(int k = -1 ; k <= 0 ; k++){
int ni = i+k, nj = j;
if(ni<1 or ni>n)continue;
white[ni].push_back(nj);
}
}
prv_root = 0;
for(int i = 1 ; i <= n ; i++){
ll prv_root = D.root[i-1];
sort(all(white[i])); COMP(white[i]);
for(auto j : white[i]){
ll cur = ++D.M;
D.upd_tree(cur,prv_root,1,m,j,1);
prv_root = cur;
}
D.root[i] = prv_root;
}
}
int colour(int x1, int y1, int x2, int y2) {
ll N = x2-x1+1, M = y2-y1+1;
ll v = (N+1)*(M+1) - (B.single_sum2(x2,y2) - B.single_sum2(x2,y1) - B.single_sum2(x1,y2) + B.single_sum2(x1,y1));
ll e = N*(M+1)+M*(N+1) - (D.single_sum3(x2-1,y2) - D.single_sum3(x2-1,y1-1) - D.single_sum3(x1-1,y2) + D.single_sum3(x1-1,y1-1)) - (R.single_sum4(x2,y2-1) - R.single_sum4(x2,y1-1) - R.single_sum4(x1-1,y2-1) + R.single_sum4(x1-1,y1-1));
ll w = W.rev_single_sum(x2,y2) - W.rev_single_sum(x2,y1-1) - W.rev_single_sum(x1-1,y2) + W.rev_single_sum(x1-1,y1-1);
return (w == N*M ? 0 : max<ll>(1,1-v+e-w));
}
