#include "bits/stdc++.h"
#include "rainbow.h"
using namespace std;
const int N=1001;
int r, c, sx, sy, m;
string s;
bool g[N][N];
int ex[N][N], ey[N][N], v[N][N], two[N][N];
int lx, ly, rx, ry;
void init(int R, int C, int sr, int sc, int M, char *S) {
r=R; c=C; sx=sr; sy=sc; m=M; s=S;
int x=sx, y=sy;
lx=rx=x;
ly=ry=y;
g[x][y]=1;
for(char c:s){
if(c=='N') x--;
if(c=='S') x++;
if(c=='W') y--;
if(c=='E') y++;
g[x][y]=1;
lx=min(lx, x);
rx=max(rx, x);
ly=min(ly, y);
ry=max(ry, y);
}
for(int i=1; i<=r; i++){
for(int j=1; j<=c; j++){
ex[i][j]=ex[i-1][j]+ex[i][j-1]-ex[i-1][j-1]+(!g[i][j]&&!g[i-1][j]);
ey[i][j]=ey[i-1][j]+ey[i][j-1]-ey[i-1][j-1]+(!g[i][j]&&!g[i][j-1]);
v[i][j]=v[i-1][j]+v[i][j-1]-v[i-1][j-1]+!g[i][j];
two[i][j]=two[i-1][j]+two[i][j-1]-two[i-1][j-1]+(!g[i][j]&&!g[i-1][j]&&!g[i][j-1]&&!g[i-1][j-1]);
}
}
}
int rect(int a[][N], int x1, int y1, int x2, int y2){
return a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
}
int colour(int ar, int ac, int br, int bc) {
int V=rect(v,ar,ac,br,bc);
int E=rect(ex,ar+1,ac,br,bc)+rect(ey,ar,ac+1,br,bc);
int F=rect(two,ar+1,ac+1,br,bc)+(ar<lx&&br>rx&&ac<ly&&bc>ry);
// cout << V << "-" << E << "+" << F << '\n';
return V-E+F;
}
// add 1 face if rectangles covers region!
