#include <bits/stdc++.h>
#include "rainbow.h"
using namespace std;
int marcaaa[5][200000], faaa;
vector< int > vlaaa,vraaa;
void init(int r, int c, int sr, int sc, int m, char *s) {
faaa = 0;
for(int i = 1; i <= r; i++)
for(int j = 1; j <= c; j++)marcaaa[i][j] = 0;
vlaaa.clear(); vraaa.clear();
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++;
marcaaa[sr][sc] = 1;
}
int l = 0;
for(int i = 1; i <= c; i++){
if(marcaaa[1][i] == 1 && marcaaa[2][i] == 1 && l == 0)l = i;
else if((marcaaa[1][i] == 0 || marcaaa[2][i]==0) && l != 0){
vlaaa.push_back(l);
vraaa.push_back(i-1);
l = 0;
}
}
if((int)vlaaa.size() == 0){
int l = 0;
for(int i = 1; i <= c; i++){
if(marcaaa[1][i] == 1){
if(l == 0)l = i;
faaa = 1;
}
if(marcaaa[2][i] == 1){
if(l == 0)l = i;
faaa = 2;
}
if(faaa!=0 && marcaaa[faaa][i] == 0){
vlaaa.push_back(l);
vraaa.push_back(i-1);
l = 0;
}
}
}
}
int colour(int ar, int ac, int br, int bc) {
if(faaa){
if(ar != br)return 1;
if(ar != faaa)return 1;
if(ac < vlaaa[0] && vraaa[0] < bc)return 2;
return 1;
}
int idl = lower_bound(vlaaa.begin(),vlaaa.end(), ac)-vlaaa.begin();
int idr = upper_bound(vraaa.begin(),vraaa.end(), bc)-vraaa.begin();
if(idl == (int)vlaaa.size() || idr == 0)return 1;
idr--;
int ans = idr-idl;
if(ac < vlaaa[idl])ans++;
if(vraaa[idr] < bc)ans++;
return ans;
}
