#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "rainbow.h"
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5 + 10;
set <pair <int, int>> V, X, Y, s;
int maxx, minx, maxy, miny;
struct range_tree {
vector <int> BIT[N], dta[N];
vector <tuple <int, int, int>> work;
void add(int x, int y, int val) {
work.push_back({x, y, val});
for (; x < N; x += x & - x)
dta[x].push_back(y);
}
void build() {
for (int i = 0; i < N; ++i) {
sort(dta[i].begin(), dta[i].end());
dta[i].erase(unique(dta[i].begin(), dta[i].end()), dta[i].end());
BIT[i].assign(dta[i].size() + 10, 0);
}
for (auto [x, y, val]: work) {
for (; x < N; x += x & - x) {
int z = lower_bound(dta[x].begin(), dta[x].end(), y) - dta[x].begin() + 1;
for (; z < BIT[x].size(); z += z & - z)
BIT[x][z] += val;
}
}
}
int get(int x, int y) {
int ans = 0;
for (; x; x -= x & - x) {
int z = upper_bound(dta[x].begin(), dta[x].end(), y) - dta[x].begin();
for (; z; z -= z & - z)
ans += BIT[x][z];
}
return ans;
}
int get(int x, int y, int u, int v) {
return get(u, v) - get(x - 1, v) - get(u, y - 1) + get(x - 1, y - 1);
}
} cnt[4];
void init(int R, int C, int x, int y, int M, char *S) {
s.insert({x, y});
maxx = minx = x;
++maxx;
maxy = miny = y;
++maxy;
for (int i = 0; i < M; ++i) {
if (S[i] == 'N') --x;
if (S[i] == 'S') ++x;
if (S[i] == 'E') ++y;
if (S[i] == 'W') --y;
maxx = max(maxx, x + 1);
minx = min(minx, x);
maxy = max(maxy, y + 1);
miny = min(miny, y);
s.insert({x, y});
}
for (auto [x, y]: s) {
V.insert({x, y});
V.insert({x, y + 1});
V.insert({x + 1, y});
V.insert({x + 1, y + 1});
X.insert({x, y});
Y.insert({x, y});
X.insert({x, y + 1});
Y.insert({x + 1, y});
}
for (auto [x, y]: s) cnt[0].add(x, y, 1);
for (auto [x, y]: V) cnt[1].add(x, y, 1);
for (auto [x, y]: X) cnt[2].add(x, y, 1);
for (auto [x, y]: Y) cnt[3].add(x, y, 1);
cnt[0].build();
cnt[1].build();
cnt[2].build();
cnt[3].build();
}
int colour(int _x, int _y, int _u, int _v) {
++_u, ++_v;
int v = cnt[1].get(_x + 1, _y + 1, _u - 1, _v - 1);
int e = cnt[2].get(_x, _y + 1, _u - 1, _v - 1) + cnt[3].get(_x + 1, _y, _u - 1, _v - 1);
int r = cnt[0].get(_x, _y, _u - 1, _v - 1);
return e - v + 1 + (_x < minx && _u > maxx && _y < miny && _v > maxy) - r;
}
////
//static int R, C, M, Q;
//static int sr, sc;
//static char S[100000 + 5];
//
//int main() {
// scanf("%d %d %d %d", &R, &C, &M, &Q);
// scanf("%d %d", &sr, &sc);
// if (M > 0) {
// scanf(" %s ", S);
// }
//
// init(R, C, sr, sc, M, S);
//
// int query;
// for (query = 0; query < Q; query++) {
// int ar, ac, br, bc;
// scanf("%d %d %d %d", &ar, &ac, &br, &bc);
// printf("%d\n", colour(ar, ac, br, bc));
// }
//
// return 0;
//}
