/**
* user: ppavic
* fname: Patrik
* lname: Pavić
* task: rainbow
* score: 12.0
* date: 2019-07-10 11:35:58.592760
*/
#include "rainbow.h"
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#define PB push_back
#define X first
#define Y second
using namespace std;
typedef pair < int, int > pt;
const int px[4] = {1, -1, 0, 0};
const int py[4] = {0, 0, 1, -1};
const int OFF = (1 << 18);
const int N = 2e5 + 500;
const int SVE = 2e7 + 500;
map < pt, bool > ima, ima2;
int toc = 0;
int cnt[SVE], L[SVE], R[SVE], TKO = 1;
int LO, HI, I;
void update(int x, int a,int b){
cnt[x]++;
if(a == b) return;
if(I <= (a + b) / 2){
int tmp = TKO++;
L[tmp] = L[L[x]];
R[tmp] = R[L[x]];
cnt[tmp] = cnt[L[x]];
L[x] = tmp;
update(L[x], a, (a + b) / 2);
}
else{
int tmp = TKO++;
L[tmp] = L[R[x]];
R[tmp] = R[R[x]];
cnt[tmp] = cnt[R[x]];
R[tmp] = tmp;
update(R[x], (a + b) / 2 + 1, b);
}
}
int query(int x1, int x2, int a,int b){
if(LO <= a && b <= HI) return (cnt[x2]) - (cnt[x1]);
if(a > HI || b < LO) return 0;
return query(L[x1], L[x2], a, (a + b) / 2) + query(R[x1], R[x2], (a + b) / 2 + 1, b);
}
struct per_tour{
int pref[10][N];
void add(vector < pt > &v){
for(pt x : v) pref[x.X][x.Y]++;
for(int i = 0;i < 10;i++){
int cur = 0;
for(int j = 0;j < N;j++){
cur += pref[i][j];
pref[i][j] = cur;
if(i) pref[i][j] += pref[i - 1][j];
}
}
}
int get2d(int x1,int x2,int y1,int y2){
if(x1 > x2 || y1 > y2) return 0;
return pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1];
}
};
per_tour deg[2], ob, ob2;
void init(int R, int C, int sr, int sc, int M, char *S) {
int cx = sr, cy = sc;
vector < pt > dod_deg0, dod_deg1, dod_ob, dod_ob2;
ima[{cx, cy}] = 1;
for(int i = 0;i < M;i++){
if(S[i] == 'N') cx--;
if(S[i] == 'S') cx++;
if(S[i] == 'W') cy--;
if(S[i] == 'E') cy++;
ima[{cx, cy}] = 1;
}
for(pair < pt, bool > A : ima){
pt x = A.X; //printf("POLJE %d %d\n", x.X, x.Y);
dod_ob.PB({x.X, x.Y});
ima2[{x.X, x.Y}] = 1;
ima2[{x.X + 1, x.Y}] = 1;
ima2[{x.X, x.Y + 1}] = 1;
ima2[{x.X + 1, x.Y + 1}] = 1;
}
toc = (int)ima2.size();
for(pair < pt, bool > A : ima2){
pt x = A.X; //printf("TOCKA %d %d\n", x.X, x.Y);
dod_ob2.PB({x.X, x.Y});
if(ima2.count({x.X + 1, x.Y}) && (ima.count({x.X, x.Y}) || ima.count({x.X, x.Y - 1})))
dod_deg0.PB({x.X, x.Y});
if(ima2.count({x.X, x.Y + 1}) && (ima.count({x.X - 1, x.Y}) || ima.count({x.X, x.Y})))
dod_deg1.PB({x.X, x.Y});
}
deg[0].add(dod_deg0);
deg[1].add(dod_deg1);
ob.add(dod_ob);
ob2.add(dod_ob2);
}
int colour(int x1, int y1, int x2, int y2) {
x2++, y2++;
int E = 0;
E += deg[0].get2d(x1 , x2 - 1, y1 + 1, y2 - 1);
E += deg[1].get2d(x1 + 1, x2 - 1, y1 , y2 - 1);
E += 2 * (x2 - x1 + y2 - y1);
int kol = ob2.get2d(x1 + 1, x2 - 1, y1 + 1, y2 - 1);
int V = kol + 2 * (x2 - x1 + y2 - y1);
//printf("V = %d E = %d\n", V, E);
int F = E - V + 2;
if(kol == toc) F++;
F--; F -= ob.get2d(x1, x2 - 1, y1, y2 - 1);
return F;
}
