#include "rainbow.h"
#include <bits/stdc++.h>
#define mp make_pair
#define F first
#define S second
#define printv(a, b) { \
for(auto pv : a) b << pv << " "; \
b << "\n"; \
}
using namespace std;
using pii = pair<int, int>;
vector<vector<bool>> g;
vector<vector<int>> vst;
int n, m;
vector<int> all, up, down;
void init(int R, int C, int sr, int sc, int M, char *S) {
n = R; m = C;
assert(n == 2);
g.resize(n + 2, vector<bool>(m + 2));
g[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++;
g[sr][sc] = true;
}
all.resize(m + 1);
up.resize(m + 1);
down.resize(m + 1);
for(int i = 1; i <= m; i++){
if(!g[1][i] && g[1][i - 1]){
up[i] = 1;
if(g[2][i] || g[2][i - 1]){
all[i] = 1;
}
}
if(!g[2][i] && g[2][i - 1]){
down[i] = 1;
if(g[1][i] || g[1][i - 1]){
all[i] = 1;
}
}
up[i] += up[i - 1];
down[i] += down[i - 1];
all[i] += all[i - 1];
}
}
int colour(int ar, int ac, int br, int bc) {
if(br == 1){
return up[bc] - up[ac] + !g[1][ac];
}
if(ar == 2){
return down[bc] - down[ac] + !g[2][ac];
}
return all[bc] - all[ac] + (!g[1][ac] || !g[2][ac]);
}
