#include <bits/stdc++.h>
#include "rainbow.h"
// #include "grader.cpp"
using namespace std;
int n, m;
vector<vector<bool>> rv;
vector<int> p2, dX = {-1, 0, 1, 0}, dY = {0, 1, 0, -1};
vector<vector<int>> p1;
void init(int R, int C, int sr, int sc, int M, char *S) {
n = R; m = C;
rv.assign(n + 2, vector<bool>(m + 2));
rv[0][0] = rv[1][0] = rv[0][m + 1] = rv[1][m + 1] = rv[sr][sc] = true;
for (int i = 0; i < M; i++) {
if (S[i] == 'N') sr--;
else if (S[i] == 'S') sr++;
else if (S[i] == 'W') sc--;
else sc++;
rv[sr][sc] = true;
}
p2.assign(m + 2, 0);
p1.assign(3, vector<int>(m + 2));
for (int i = 1; i <= m; i++) {
p1[1][i] = p1[1][i - 1] + (!rv[1][i - 1] && rv[1][i]);
p1[2][i] = p1[2][i - 1] + (!rv[2][i - 1] && rv[2][i]);
p2[i] = p2[i - 1] + (rv[1][i] && rv[2][i] && !rv[1][i - 1] && !rv[2][i - 1]);
if (!rv[1][i] && rv[1][i + 1] && rv[2][i]) p2[i]++;
if (rv[1][i] && !rv[2][i] && rv[2][i + 1]) p2[i]++;
}
}
int colour(int ar, int ac, int br, int bc) {
if (ar == br) return p1[ar][bc] - p1[ar][ac] + !rv[ar][bc];
bool tr1 = (rv[1][bc] && rv[2][bc] && !rv[1][bc - 1] && !rv[2][bc - 1]);
bool tr2 = (rv[1][ac] && rv[2][ac] && !rv[1][ac - 1] && !rv[2][ac - 1]);
return p2[bc - 1] - p2[ac - 1] + tr1 - tr2 + (!rv[1][bc] || !rv[2][bc]);
}
