// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout<<#x<<" = "<<x<<endl
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
const int INF = 1'000'000'007;
#include "rainbow.h"
int dr[]={1,-1,0,0};
int dc[]={0,0,1,-1};
int rows,cols,AR,AC,BR,BC;
vector<vector<bool>> grid,vis;
bool valid(int row,int col) { return AR<=row&&row<BR&&AC<=col&&col<BC; }
void dfs(int row,int col) {
vis[row][col]=1;
//cout<<"row = "<<row<<" col = "<<col<<" grid = "<<grid[row][col]<<endl;
rep(k,0,4) {
int nr=row+dr[k],nc=col+dc[k];
if(valid(nr,nc)&&!vis[nr][nc]&&!grid[nr][nc]) dfs(nr,nc);
}
}
void init(int R, int C, int sr, int sc, int M, char *S) {
rows=R;
cols=C;
--sr; --sc;
rep(i,0,M) {
if(S[i]=='S') S[i]=0;
if(S[i]=='N') S[i]=1;
if(S[i]=='E') S[i]=2;
if(S[i]=='W') S[i]=3;
}
if(rows<=50&&cols<=50) {
grid.assign(R,vector<bool>(C,0));
grid[sr][sc]=1;
rep(i,0,M) {
sr+=dr[S[i]];
sc+=dc[S[i]];
grid[sr][sc]=1;
}
//rep(i,0,rows) {
// rep(j,0,cols) cout<<grid[i][j]<<' ';
// cout<<endl;
//}
//cout<<endl;
}
}
int colour(int ar, int ac, int br, int bc) {
int ans=0;
if(rows<=50&&cols<=50) {
--ar; --ac;
AR=ar;
AC=ac;
BR=br;
BC=bc;
vis.assign(rows,vector<bool>(cols,0));
rep(i,ar,br) {
rep(j,ac,bc) {
if(vis[i][j]||grid[i][j]) continue;
++ans;
dfs(i,j);
}
}
}
return ans;
}
/*
#include "rainbow.h"
#include <stdio.h>
static int R, C, M, Q;
static int sr, sc;
static char S[100000 + 5];
int main() {
scanf("%d %d %d %d", &R, &C, &M, &Q);
scanf("%d %d", &sr, &sc);
if (M > 0) {
scanf(" %s ", S);
}
init(R, C, sr, sc, M, S);
int query;
for (query = 0; query < Q; query++) {
int ar, ac, br, bc;
scanf("%d %d %d %d", &ar, &ac, &br, &bc);
printf("%d\n", colour(ar, ac, br, bc));
}
return 0;
}
*/
