#include <bits/stdc++.h>
using namespace std;
#include "rainbow.h"
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef pair<int, int> ii;
const int len = 2e5+5;
int n, m, min_r = len, max_r = 0, min_c = len, max_c = 0;
struct bit{
vector<int> vec[len];
int row, col;
bit(int x = 0, int y = 0){
row = x;
col = y;
}
void init(){
for (int i = row; i >= 1; i--){
sort(vec[i].begin(), vec[i].end());
vec[i].erase(unique(vec[i].begin(), vec[i].end()), vec[i].end());
for (int j = i+(i&(-i)); j <= row; j += i&(-i))
for (auto &c: vec[i]) vec[j].pb(c);
}
for (int i = 1; i <= row; i++)
sort(vec[i].begin(), vec[i].end());
}
void upd(int i, int j){
vec[i].pb(j);
}
int ask(int i, int l, int r){
int ans = 0;
while (i > 0){
ans += upper_bound(vec[i].begin(), vec[i].end(), r) - lower_bound(vec[i].begin(), vec[i].end(), l);
i -= i&(-i);
}
return ans;
}
int query(int ar, int br, int ac, int bc){
return ask(br, ac, bc) - ask(ar-1, ac, bc);
}
void print(int row){
printf("row#%d:", row);
for (int j = 0; j < vec[row].size(); j++)
printf(" %d", vec[row][j]);
printf("\n");
}
};
bit vertices, rivers;
bit vertical, horizontal;
void nex_mov(int &x, int &y, char &c){
if (c == 'N')
x--;
else if (c == 'S')
x++;
else if (c == 'W')
y--;
else
y++;
}
void add_block(int x, int y){
min_r = min(min_r, x);
max_r = max(max_r, x);
min_c = min(min_c, y);
max_c = max(max_c, y);
rivers.upd(x, y);
vertices.upd(x, y);
vertices.upd(x+1, y);
vertices.upd(x, y+1);
vertices.upd(x+1, y+1);
vertical.upd(x, y);
vertical.upd(x, y+1);
horizontal.upd(x, y);
horizontal.upd(x+1, y);
}
void make_graph(int x, int y, char *moves){
int pos = 0;
while (true){
add_block(x, y);
if (moves[pos] == '\0')
break;
nex_mov(x, y, moves[pos++]);
}
}
void init(int n_, int m_, int sr, int sc, int M, char *moves) {
n = n_, m = m_;
vertices = bit(n+1, m+1);
rivers = bit(n, m);
vertical = bit(n, m+1);
horizontal = bit(n+1, m);
make_graph(sr, sc, moves);
vertices.init();
rivers.init();
vertical.init();
horizontal.init();
}
int colour(int ar, int ac, int br, int bc) {
int v = vertices.query(ar+1, br, ac+1, bc); // + 2*(length+width)
int e = vertical.query(ar, br, ac+1, bc); // + 2*length
e += horizontal.query(ar+1, br, ac, bc); // + 2*width
int r = rivers.query(ar, br, ac, bc);
int c = (ar < min_r && max_r < br && ac < min_c && max_c < bc)?2:1;
//printf("v = %d, e = %d, r = %d, c = %d\n", v, e, r, c);
return e + c - v - r;
}
