#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1<<18
const int SZ = MAXN;
template<class T> struct node {
T val = 0; node<T>* c[2];
node() { c[0] = c[1] = NULL; }
void upd(int ind, T v, int L = 0, int R = SZ-1) { // add v
if (L == ind && R == ind) { val += v; return; }
int M = (L+R)/2;
if (ind <= M) {
if (!c[0]) c[0] = new node();
c[0]->upd(ind,v,L,M);
} else {
if (!c[1]) c[1] = new node();
c[1]->upd(ind,v,M+1,R);
}
val = 0; for(int i = 0; i<2; i++) if (c[i]) val += c[i]->val;
}
T query(int lo, int hi, int L = 0, int R = SZ-1) { // query sum of segment
if (hi < L || R < lo) return 0;
if (lo <= L && R <= hi) return val;
int M = (L+R)/2; T res = 0;
if (c[0]) res += c[0]->query(lo,hi,L,M);
if (c[1]) res += c[1]->query(lo,hi,M+1,R);
return res;
}
void UPD(int ind, node* c0, node* c1, int L = 0, int R = SZ-1) { // for 2D segtree
if (L != R) {
int M = (L+R)/2;
if (ind <= M) {
if (!c[0]) c[0] = new node();
c[0]->UPD(ind,c0?c0->c[0]:NULL,c1?c1->c[0]:NULL,L,M);
} else {
if (!c[1]) c[1] = new node();
c[1]->UPD(ind,c0?c0->c[1]:NULL,c1?c1->c[1]:NULL,M+1,R);
}
}
val = (c0?c0->val:0)+(c1?c1->val:0);
}
};
template<class T> struct Node {
node<T> seg; Node* c[2];
Node() { c[0] = c[1] = NULL; }
void upd(int x, int y, T v, int L = 0, int R = SZ-1) { // add v
if (L == x && R == x) { seg.upd(y,v); return; }
int M = (L+R)/2;
if (x <= M) {
if (!c[0]) c[0] = new Node();
c[0]->upd(x,y,v,L,M);
} else {
if (!c[1]) c[1] = new Node();
c[1]->upd(x,y,v,M+1,R);
}
seg.upd(y,v); // only for addition
// seg.UPD(y,c[0]?&c[0]->seg:NULL,c[1]?&c[1]->seg:NULL);
}
T query(int x1, int x2, int y1, int y2, int L = 0, int R = SZ-1) { // query sum of rectangle
if (x1 <= L && R <= x2) return seg.query(y1,y2);
if (x2 < L || R < x1) return 0;
int M = (L+R)/2; T res = 0;
if (c[0]) res += c[0]->query(x1,x2,y1,y2,L,M);
if (c[1]) res += c[1]->query(x1,x2,y1,y2,M+1,R);
return res;
}
};
map<pair<int, int>, int> mp;
set<pair<int, int>> visited;
vector<int> trows[MAXN];
vector<int> tcols[MAXN];
vector<pair<int, int>> rows[MAXN];
vector<pair<int, int>> cols[MAXN];
Node<int> seg;
int minr = MAXN, maxr = -MAXN, minc = MAXN, maxc = -MAXN;
void addSquare(int a, int b){
if(visited.count({a, b})) return;
visited.insert({a, b});
mp[{a, b}]++;
mp[{a+1, b}]++;
mp[{a, b+1}]++;
mp[{a+1, b+1}]++;
trows[a].push_back(b);
tcols[b].push_back(a);
minr = min(minr, a); maxr = max(maxr, a);
minc = min(minc, b); maxc = max(maxc, b);
}
void init(int R, int C, int sr, int sc, int M, char *S) {
string s = S;
addSquare(sr, sc);
for(auto c : s){
if(c == 'N') sr--;
if(c == 'S') sr++;
if(c == 'W') sc--;
if(c == 'E') sc++;
addSquare(sr, sc);
}
for(auto p : mp){
if(p.second == 1) seg.upd(p.first.first, p.first.second, 1);
if(p.second == 3) seg.upd(p.first.first, p.first.second, -1);
if(p.second == 2){
if(visited.count({p.first.first, p.first.second}) && visited.count({p.first.first-1, p.first.second-1})) seg.upd(p.first.first, p.first.second, -2);
if(visited.count({p.first.first-1, p.first.second}) && visited.count({p.first.first, p.first.second-1})) seg.upd(p.first.first, p.first.second, -2);
}
}
for(int i = 0; i<MAXN; i++) sort(trows[i].begin(), trows[i].end());
for(int i = 0; i<MAXN; i++) sort(tcols[i].begin(), tcols[i].end());
for(int i = 0; i<MAXN; i++){
if(trows[i].empty()) continue;
int cur = trows[i][0];
for(int j = 1; j<trows[i].size(); j++){
if(trows[i][j] != trows[i][j-1]+1){
rows[i].push_back({cur, trows[i][j-1]});
cur = trows[i][j];
}
}
rows[i].push_back({cur, trows[i].back()});
}
for(int i = 0; i<MAXN; i++){
if(tcols[i].empty()) continue;
int cur = tcols[i][0];
for(int j = 1; j<tcols[i].size(); j++){
if(tcols[i][j] != tcols[i][j-1]+1){
cols[i].push_back({cur, tcols[i][j-1]});
cur = tcols[i][j];
}
}
cols[i].push_back({cur, tcols[i].back()});
}
// for(int i = 0; i<MAXN; i++){
// if(cols[i].empty()) continue;
// cout << i << endl;
// for(auto j : cols[i]) cout << j.first << " " << j.second << endl;
// cout << endl;
// }
}
int colour(int ar, int ac, int br, int bc) {
int ans = 0;
ans += seg.query(ar+1, br, ac+1, bc);
int p1, p2;
// top row
p1 = lower_bound(rows[ar].begin(), rows[ar].end(), make_pair(ac+1, -1))-rows[ar].begin();
p2 = lower_bound(rows[ar].begin(), rows[ar].end(), make_pair(bc+1, -1))-rows[ar].begin();
p1--; p2--;
if(p1 >= 0 && rows[ar][p1].second >= ac && rows[ar][p1].second < bc) ans--;
if(p2 >= 0 && rows[ar][p2].first > ac && rows[ar][p2].second >= bc) ans--;
p1++; if(p2 >= 0 && rows[ar][p2].second >= bc) p2--;
if(p1 < rows[ar].size() && rows[ar][p1].second < bc && p2 >= 0 && rows[ar][p2].first > ac) ans -= (p2-p1+1)*2;
p1 = lower_bound(rows[br].begin(), rows[br].end(), make_pair(ac+1, -1))-rows[br].begin();
p2 = lower_bound(rows[br].begin(), rows[br].end(), make_pair(bc+1, -1))-rows[br].begin();
p1--; p2--;
if(p1 >= 0 && rows[br][p1].second >= ac && rows[br][p1].second < bc) ans--;
if(p2 >= 0 && rows[br][p2].first > ac && rows[br][p2].second >= bc) ans--;
p1++; if(p2 >= 0 && rows[br][p2].second >= bc) p2--;
if(p1 < rows[br].size() && rows[br][p1].second < bc && p2 >= 0 && rows[br][p2].first > ac) ans -= (p2-p1+1)*2;
p1 = lower_bound(cols[ac].begin(), cols[ac].end(), make_pair(ar+1, -1))-cols[ac].begin();
p2 = lower_bound(cols[ac].begin(), cols[ac].end(), make_pair(br+1, -1))-cols[ac].begin();
p1--; p2--;
if(p1 >= 0 && cols[ac][p1].second >= ar && cols[ac][p1].second < br) ans--;
if(p2 >= 0 && cols[ac][p2].first > ar && cols[ac][p2].second >= br) ans--;
p1++; if(p2 >= 0 && cols[ac][p2].second >= br) p2--;
if(p1 < cols[ac].size() && cols[ac][p1].second < br && p2 >= 0 && cols[ac][p2].first > ar) ans -= (p2-p1+1)*2;
p1 = lower_bound(cols[bc].begin(), cols[bc].end(), make_pair(ar+1, -1))-cols[bc].begin();
p2 = lower_bound(cols[bc].begin(), cols[bc].end(), make_pair(br+1, -1))-cols[bc].begin();
p1--; p2--;
if(p1 >= 0 && cols[bc][p1].second >= ar && cols[bc][p1].second < br) ans--;
if(p2 >= 0 && cols[bc][p2].first > ar && cols[bc][p2].second >= br) ans--;
p1++; if(p2 >= 0 && cols[bc][p2].second >= br) p2--;
if(p1 < cols[bc].size() && cols[bc][p1].second < br && p2 >= 0 && cols[bc][p2].first > ar) ans -= (p2-p1+1)*2;
if(!visited.count({ar, ac})) ans--;
if(!visited.count({ar, bc})) ans--;
if(!visited.count({br, ac})) ans--;
if(!visited.count({br, bc})) ans--;
if(ar < minr && br > maxr && ac < minc && bc > maxc) ans -= 4;
return -ans/4;
}
