#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long int LLI;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
#include "rainbow.h"
int r,c;
vpii p;
int grid[2][200000];
vpii r1,r2,r12;
void init(int R,int C,int sr,int sc,int M,char *S) {
int i;
r = R,c = C;
sr--,sc--;
p.pb(mp(sr,sc));
for (i = 0; i < M; i++) {
if (S[i] == 'N') sr--;
else if (S[i] == 'S') sr++;
else if (S[i] == 'W') sc--;
else sc++;
p.pb(mp(sr,sc));
}
sort(p.begin(),p.end());
p.resize(unique(p.begin(),p.end())-p.begin());
//cout<<"hhh"<<endl;
//for (i=0;i<p.size();i++)cout<<p[i].first<<","<<p[i].second<<endl;
if (R == 2) {
for (i = 0; i < p.size(); i++) grid[p[i].first][p[i].second] = 1;
int pre = -1;
for (i = 0; i < C; i++) {
if (grid[0][i]) {
if (pre != (i-1)) r1.pb(mp(pre+1,i-1));
pre = i;
}
}
if (pre != C-1) r1.pb(mp(pre+1,C-1));
pre = -1;
for (i = 0; i < C; i++) {
if (grid[1][i]) {
if (pre != (i-1)) r2.pb(mp(pre+1,i-1));
pre = i;
}
}
if (pre != C-1) r2.pb(mp(pre+1,C-1));
pre = -1;
for (i = 0; i < C; i++) {
if (grid[0][i] && grid[1][i]) {
if (pre != (i-1)) r12.pb(mp(pre+1,i-1));
pre = i;
}
}
if (pre != C-1) r12.pb(mp(pre+1,C-1));
//cout<<"hhhh"<<endl;
}
else {
}
}
int colour(int ar,int ac,int br,int bc) {
ar--,ac--,br--,bc--;
if (r == 2) {
vpii *_use;
//cout<<"here"<<endl;
if ((ar == 0) && (br == 0)) _use = &r1;
else if ((ar == 0) && (br == 1)) _use = &r12;
else _use = &r2;
//cout<<"here"<<endl;
vpii &use = *_use;
//for (int i = 0;i<use.size();i++)cout<<use[i].first<<","<<use[i].second<<" ";
int l = lower_bound(use.begin(),use.end(),mp(ac,0))-use.begin()-1;
if ((l == -1) || (use[l].second < ac)) l++;
int r = upper_bound(use.begin(),use.end(),mp(bc,c))-use.begin()-1;
return r-l+1;
}
return 1;
}
