#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int v[3][MAXN], cor[3][3][MAXN];
int erro[4][MAXN], soma[4][MAXN];
int kc[3][3];
int n, m;
void dfs(int k, int ind, int val) {
for(int i=ind; i<=m; i++) {
if(v[k][i]) return;
cor[1][k][i]=val;
}
}
void dfs2(int ox, int oy, int val) {
cor[2][ox][oy]=val; int outro=((ox)%2)+1;
if(cor[2][outro][oy]==0&&v[outro][oy]!=1) dfs2(outro, oy, val);
if(oy+1>m) return;
if(cor[2][ox][oy+1]==0&&v[ox][oy+1]!=1) dfs2(ox, oy+1, val);
}
void init(int R, int C, int sr, int sc, int M, char *S) {
int cx=sr, cy=sc; n=R; m=C;
v[cx][cy]=1;
for(int i=0; i<M; i++) {
if(S[i]=='N') cx--;
if(S[i]=='S') cx++;
if(S[i]=='W') cy--;
if(S[i]=='E') cy++;
v[cx][cy]=1;
}
kc[1][1]=1; kc[1][2]=1; kc[2][2]=1;
for(int i=1; i<=C; i++) {
for(int k=1; k<=2; k++) {
if(cor[1][k][i]==0&&!v[k][i]) dfs(k, i, kc[1][k]++);
if(cor[2][k][i]==0&&!v[k][i]) dfs2(k, i, kc[2][2]++);
}
soma[1][i]=max(cor[1][1][i], soma[1][i-1]);
soma[2][i]=max(cor[1][2][i], soma[2][i-1]);
soma[3][i]=max(soma[3][i-1], max(cor[2][1][i], cor[2][2][i]));
}
for(int k=1; k<=2; k++) {
//for(int i=1; i<=m; i++) printf("%d ", soma[k][i]); printf("\n");
}
}
int colour(int ar, int ac, int br, int bc) {
if(ar==br) {
int resp=soma[ar][bc]-soma[ar][ac]+1;
if(v[ar][ac]) resp--;
return resp;
}
else {
int resp=soma[3][bc]-soma[3][ac]+1;
if(v[1][ac]&&v[2][ac]) resp--;
return resp;
}
return 0;
}
