#include "rainbow.h"
#include<bits/stdc++.h>
#define lf double
#define ll long long
#define cc pair<char,char>
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000007
#define inf 1000000000
#define MAXN 200005
#define LOG 20
#define magic 100
#define KOK 350
#define EPS 0.0025
#define pw(x) ((1ll)<<(x))
#define PI 3.1415926535
using namespace std;
struct seg {
int pre;
int suf;
int ins;
int full;
} Sg[MAXN*4];
int lazy[MAXN*4];
int reg,R,C;
int bol[3][MAXN],nxt[3][MAXN],prv[3][MAXN],pres[3][MAXN];
bool vis[3][MAXN],a[3][MAXN];
vector<iii> qu[MAXN];
vector<int> eve[MAXN];
int w[4][2]={1,0,0,1,-1,0,0,-1};
void inc(int &x,int &y,char c) {
if(c=='N') x--;
if(c=='S') x++;
if(c=='W') y--;
if(c=='E') y++;
}
void clear(int x,int y) {
for(int i=0;i<=x;i++) for(int j=0;j<=y;j++) vis[i][j]=bol[i][j]=0;
reg=0;
}
void push(int node) {
if(!lazy[node]) return ;
lazy[node*2]=lazy[node];
lazy[node*2+1]=lazy[node];
lazy[node]=0;
}
seg merge(seg x,seg y) {
seg res;
res.pre=x.pre+(x.full)*y.pre;
res.suf=y.suf+(y.full)*x.suf;
res.full=(x.full&y.full);
res.ins=x.ins+y.ins+(x.suf>0 && y.pre>0 && !x.full && !y.full);
return res;
}
seg get(int node,int bas,int son,int x,int y,int flag) {
if(!flag) flag=lazy[node];
if(bas>=x && son<=y) {
if(flag==1) return {son-bas+1,son-bas+1,0,1};
if(flag==2) return {0,0,0,0};
return Sg[node];
}
if(y<=orta) return get(node*2,bas,orta,x,y,flag);
if(x>orta) return get(node*2+1,orta+1,son,x,y,flag);
return merge(get(node*2,bas,orta,x,y,flag),get(node*2+1,orta+1,son,x,y,flag));
}
void up(int node,int bas,int son,int x,int y,int val) {
if(bas>y || son<x) return ;
if(bas>=x && son<=y) {
lazy[node]=val;
return ;
}
push(node);
up(node*2,bas,orta,x,y,val);
up(node*2+1,orta+1,son,x,y,val);
seg l,r;
if(lazy[node*2]==2) l={0,0,0,0};
else if(lazy[node*2]==1) l={orta-bas+1,orta-bas+1,0,1};
else l=Sg[node*2];
if(lazy[node*2+1]==2) r={0,0,0,0};
else if(lazy[node*2+1]==1) r={son-orta,son-orta,0,1};
else r=Sg[node*2+1];
Sg[node]=merge(l,r);
}
void build(int node,int bas,int son) {
lazy[node]=0;
if(bas==son) {
Sg[node]={1,1,0,1};
return ;
}
build(node*2,bas,orta);
build(node*2+1,orta+1,son);
Sg[node]=merge(Sg[node*2],Sg[node*2+1]);
}
void dfs(int x,int y,int lx,int ly,int rx,int ry) {
if(vis[x][y] || a[x][y]) return ;
if(x>rx || x<lx || y>ry || y<ly) return ;
bol[x][y]=reg;
vis[x][y]=1;
for(int i=0;i<4;i++) dfs(x+w[i][0],y+w[i][1],lx,ly,rx,ry);
}
void fillnaive(int R,int C,int sr,int sc,int M,char *S) {
a[sr][sc]=1;
for(int i=0;i<M;i++) {
inc(sr,sc,S[i]);
a[sr][sc]=1;
}
clear(R,C);
for(int j=1;j<=C;j++) {
for(int i=1;i<=R;i++) {
if(!vis[i][j] && !a[i][j]) {
reg++;
dfs(i,j,1,1,R,C);
}
}
}
for(int i=1;i<=R;i++) {
for(int j=1;j<=C;j++) {
if(!a[i][j] && (a[i][j-1] || j-1==0)) pres[i][j]=pres[i][j-1]+1;
else pres[i][j]=pres[i][j-1];
}
}
for(int i=1;i<=R;i++) {
nxt[i][C+1]=inf;
prv[i][0]=-inf;
for(int j=C;j>=1;j--) {
if(bol[i][j]) nxt[i][j]=bol[i][j];
else nxt[i][j]=nxt[i][j+1];
}
for(int j=1;j<=C;j++) {
if(bol[i][j]) prv[i][j]=bol[i][j];
else prv[i][j]=prv[i][j-1];
}
}
}
void init(int R, int C, int sr, int sc, int M, char *S) {
::R=R;
::C=C;
if(R<=2) {
fillnaive(R,C,sr,sc,M,S);
}
else {
eve[sr].pb(sc);
for(int i=0;i<M;i++) {
inc(sr,sc,S[i]);
eve[sr].pb(sc);
}
for(int i=1;i<MAXN;i++) {
eve[i].erase(unique(all(eve[i])),eve[i].end());
if(!sz(eve[i])) {
qu[i].pb({{0,MAXN-1},0});
continue ;
}
qu[i].pb({{0,eve[i][0]-1},0});
for(int j=0;j<sz(eve[i]);j++) {
int bas=j;
while(j+1<sz(eve[i]) && eve[i][j]+1==eve[i][j+1]) j++;
qu[i].pb({{eve[i][bas],eve[i][j]},1});
if(j+1<sz(eve[i])) {
qu[i].pb({{eve[i][j]+1,eve[i][j+1]-1},0});
}
else {
qu[i].pb({{eve[i][j]+1,MAXN-1},0});
}
}
}
}
}
void process(int &res,iii j,int ac,int bc,bool flag) {
if(j.st.nd<ac || j.st.st>bc) return ;
int l=max(j.st.st,ac);
int r=min(j.st.nd,bc);
if(l>r) return ;
if(j.nd && flag) {
seg query=get(1,ac,bc,l,r,0);
res+=query.ins+(query.pre>0)+(query.suf>0)-query.full;
}
up(1,ac,bc,l,r,j.nd+1);
}
int colour(int ar, int ac, int br, int bc) {
if(R<=2) {
if(ar!=br) {
int r1=min(nxt[ar][ac],nxt[br][ac]);
int r2=max(prv[br][bc],prv[ar][bc]);
if(r1==inf || r2==-inf) return 0;
return max(0,r2-r1+1);
}
return pres[ar][bc]-pres[ar][ac-1]+(!a[ar][ac] && !a[ar][ac-1] && ac>1);
}
build(1,ac,bc);
int res=0;
for(int i=ar;i<=br;i++) {
for(iii j:qu[i]) {
process(res,j,ac,bc,i>ar);
}
}
process(res,{{ac,bc},1},ac,bc,1);
return res;
}
