//Subtask 2
#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 2e5 + 5;
int n,m,k;
int a[3][maxn];
map<int,pii> itv[5];
void init(int R, int C, int sr, int sc, int M, char *S) {
n = R; m = C; k = M;
int x = sr, y = sc;
a[x][y] = 1;
for(int i=0;i<k;i++) {
if(S[i]=='N') x--;
if(S[i]=='E') y++;
if(S[i]=='W') y--;
if(S[i]=='S') x++;
a[x][y] = 1;
}
int sz;
sz = 0;
for(int y=1;y<=m;y++) {
if(a[1][y]) continue;
int pos = y;
while(y+1<=m && !a[1][y+1]) y++;
// printf("1 [%d, %d]\n",pos,y);
itv[1][y] = {pos,++sz};
}
itv[1][m+1] = {m+1, ++sz};
sz = 0;
for(int y=1;y<=m;y++) {
if(a[2][y]) continue;
int pos = y;
while(y+1<=m && !a[2][y+1]) y++;
// printf("2 [%d, %d]\n",pos,y);
itv[2][y] = {pos,++sz};
}
itv[2][m+1] = {m+1,++sz};
sz = 0;
for(int y=1;y<=m;y++) {
if(a[1][y] && a[2][y]) continue;
int pos = y;
while(y+1<=m && ((!a[1][y]&&!a[1][y+1]) || (!a[2][y]&&!a[2][y+1]))) y++;
// printf("3 [%d, %d]\n",pos,y);
itv[3][y] = {pos,++sz};
}
itv[3][m+1] = {m+1,++sz};
}
int colour(int ar, int ac, int br, int bc) {
int t;
if(ar==1 && br==1) t = 1;
else if(ar==2 && br==2) t = 2;
else t = 3;
auto it1 = itv[t].lower_bound(ac);
auto it2 = itv[t].lower_bound(bc);
int res = it2->Y.Y - it1->Y.Y + 1;
if(it2->Y.X > bc) res--;
return res;
}
