/*
The planar graph : First, draw a "bound river" rectangle
For example, the query :
("r" means river cell, "." means empty cell)
....rrrrr..
rrr....r...
..r....rrr.
rrr.....r..
Draw a "bound river" rectangle
=>
rrrrrrrrrrrrr
r....rrrrr..r
rrrr....r...r
r..r....rrr.r
rrrr.....r..r
rrrrrrrrrrrrr
- vertexes = number of r
- edges = number of adjacent pairs r <-> r
- *faces = number of 2x2s of r
- connected components = if the whole river is "strictly" inside the rectangle => connected components = 2, otherwise cc = 1
- answer = *faces - *(number of block 2x2s of r)
For example :
rrrrrrrr
r......r
r..rr..r
r......r
rrrrrrrr
so cc = 2
Special Case :
..rrrr
..r..r
...rrr
just need 1 more segment tree 2d
Euler Polyhedron Formula : V - E + F = 1 + C
*/
#include "bits/stdc++.h"
#ifndef LOCAL
#include "rainbow.h"
#endif
using namespace std;
#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
template<typename T>
bool minimize(T& a, const T& b){
if(a > b){
return a = b, true;
}
return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b){
return a = b, true;
}
return false;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;
const int MAX = 1e5 + 5;
const int MAXNODES = MAX * 5 * 17;
int used;
struct node{
int ln, rn, sum;
} st[MAXNODES];
int build(int l, int r){
if(l == r) return ++used;
int mid = l + r >> 1, cur = ++used;
st[cur].ln = build(l, mid);
st[cur].rn = build(mid + 1, r);
return cur;
}
void refine(int nd){
st[nd].sum = st[st[nd].ln].sum + st[st[nd].rn].sum;
}
int update(int nd, int l, int r, int pos, int val){
if(l == r){
++used;
st[used].sum = st[nd].sum + val;
return used;
} else{
int mid = l + r >> 1, cur = ++used;
st[cur].ln = st[nd].ln;
st[cur].rn = st[nd].rn;
if(pos <= mid) st[cur].ln = update(st[nd].ln, l, mid, pos, val);
else st[cur].rn = update(st[nd].rn, mid + 1, r, pos, val);
refine(cur);
return cur;
}
}
int query(int vl, int vr, int l, int r, int u, int v){
if(v < l || u > r) return 0;
if(u <= l && r <= v) return st[vr].sum - st[vl].sum;
int mid = l + r >> 1;
return query(st[vl].ln, st[vr].ln, l, mid, u, v) + query(st[vl].rn, st[vr].rn, mid + 1, r, u, v);
}
struct tree2d{
int bound;
vector<int> rt;
vector<pair<int, int>> pts;
tree2d() : rt(), pts(), bound() {}
tree2d(int n, int m) : rt(n + 1), bound(m), pts() {}
void add(const pair<int, int>& p){
pts.emplace_back(p);
}
void construct(){
if(bound == 0) return;
sort(all(pts));
rt[0] = build(1, bound);
for(int i = 1, j = 0; i < sz(rt); ++i){
rt[i] = rt[i - 1];
while(j < sz(pts) && pts[j].first == i){
rt[i] = update(rt[i], 1, bound, pts[j].second, +1);
++j;
}
}
}
int query2d(int l, int r, int u, int v){
if(l > r || u > v) return 0;
return query(rt[l - 1], rt[r], 1, bound, u, v);
}
} horizontal_edges, vertical_edges, vertices, blocks, special_edges;
int min_x, max_x, min_y, max_y;
void init(int R, int C, int x, int y, int M, char *S) {
set<pair<int, int>> rivers;
min_x = 1e9;
max_x = -1e9;
min_y = 1e9;
max_y = -1e9;
for(int i = 0; i <= M; ++i){
rivers.insert({x, y});
minimize(min_x, x);
maximize(max_x, x);
minimize(min_y, y);
maximize(max_y, y);
if(i < M){
if(S[i] == 'N') --x;
if(S[i] == 'S') ++x;
if(S[i] == 'W') --y;
if(S[i] == 'E') ++y;
}
}
horizontal_edges = tree2d(R, C);
vertical_edges = tree2d(R, C);
vertices = tree2d(R, C);
blocks = tree2d(R, C);
special_edges = tree2d(R, C);
for(auto [x, y] : rivers){
vertices.add({x, y});
//(x + 1, y) -> vertical
bool vert = false, horz = false;
if(rivers.count({x, y + 1})){
vertical_edges.add({x, y});
vert = true;
}
//(x, y + 1) -> horizontal
if(rivers.count({x + 1, y})){
horizontal_edges.add({x, y});
horz = true;
}
if(vert && horz && rivers.count({x + 1, y + 1})){
blocks.add({x, y});
}
if(rivers.count({x - 1, y + 1}) && !rivers.count({x - 1, y}) && !rivers.count({x, y + 1})){
special_edges.add({x - 1, y});
}
if(rivers.count({x + 1, y + 1}) && !rivers.count({x + 1, y}) && !rivers.count({x, y + 1})){
special_edges.add({x, y});
}
}
horizontal_edges.construct();
vertical_edges.construct();
vertices.construct();
blocks.construct();
special_edges.construct();
}
int count_vertices(int x1, int y1, int x2, int y2){
int cur = vertices.query2d(x1, x2, y1, y2);
int side = ((x2 - x1 + 1) + (y2 - y1 + 1)) * 2 + 4;
return cur + side;
}
int count_edges(int x1, int y1, int x2, int y2){
int side = ((x2 - x1 + 1) + (y2 - y1 + 1)) * 2 + 4;
int horz = horizontal_edges.query2d(x1, x2 - 1, y1, y2);
int vert = vertical_edges.query2d(x1, x2, y1, y2 - 1);
int left_side = vertices.query2d(x1, x1, y1, y2);
int right_side = vertices.query2d(x2, x2, y1, y2);
int up_side = vertices.query2d(x1, x2, y1, y1);
int down_side = vertices.query2d(x1, x2, y2, y2);
int extra = special_edges.query2d(x1, x2 - 1, y1, y2 - 1);
return side + horz + vert + left_side + right_side + up_side + down_side + extra;
}
int count_connected_components(int x1, int y1, int x2, int y2){
int extra = (x1 < min_x && max_x < x2 && y1 < min_y && max_y < y2);
return 1 + extra;
}
int count_blocks(int x1, int y1, int x2, int y2){
int inside = blocks.query2d(x1, x2 - 1, y1, y2 - 1);
int l = vertical_edges.query2d(x1, x1, y1, y2 - 1);
int r = vertical_edges.query2d(x2, x2, y1, y2 - 1);
int d = horizontal_edges.query2d(x1, x2 - 1, y1, y1);
int u = horizontal_edges.query2d(x1, x2 - 1, y2, y2);
int x1y1 = vertices.query2d(x1, x1, y1, y1);
int x1y2 = vertices.query2d(x1, x1, y2, y2);
int x2y1 = vertices.query2d(x2, x2, y1, y1);
int x2y2 = vertices.query2d(x2, x2, y2, y2);
return inside + l + r + d + u + x1y1 + x1y2 + x2y1 + x2y2;
}
int colour(int ar, int ac, int br, int bc){
int V = count_vertices(ar, ac, br, bc);
int E = count_edges(ar, ac, br, bc);
int C = count_connected_components(ar, ac, br, bc);
int blocks = count_blocks(ar, ac, br, bc);
return E - V + C - blocks;
}
#ifdef LOCAL
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
int R, C, M, Q, sr, sc;
cin >> R >> C >> M >> Q >> sr >> sc;
char S[M];
for(int i = 0; i < M; ++i) cin >> S[i];
init(R, C, sr, sc, M, S);
while(Q--){
int ar, ac, br, bc;
cin >> ar >> ac >> br >> bc;
cout << colour(ar, ac, br, bc) << '\n';
}
return 0;
}
#endif // LOCAL
