#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int mxN=2e5, INF=69696969;
int n, m, lr=INF, rr=-1, lc=INF, rc=-1;
set<int> vis[mxN];
vector<int> row_edge[mxN], col_edge[mxN], faces[mxN];
bool ok(int i, int j) {
return 0<=i&&i<n&&0<=j&&j<m&&vis[i].find(j)==vis[i].end();
}
void consider(int i, int j) {
if (vis[i].find(j)==vis[i].end()) {
lr=min(lr, i), rr=max(rr, i);
lc=min(lc, j), rc=max(rc, j);
if (ok(i, j-1)) row_edge[i].push_back(j-1);
if (ok(i, j+1)) row_edge[i].push_back(j);
if (ok(i-1, j)) col_edge[i-1].push_back(j);
if (ok(i+1, j)) col_edge[i].push_back(j);
for (int a : {i-1, i})
for (int b : {j-1, j})
if (ok(a, b)&&ok(a+1, b)&&ok(a, b+1)&&ok(a+1, b+1))
faces[a].push_back(b);
vis[i].insert(j);
}
}
struct Node {
int s=0;
Node *left=nullptr, *right=nullptr;
Node(int l, int r) {
if (l!=r) {
int mid=(l+r)/2;
left=new Node(l, mid);
right=new Node(mid+1, r);
}
}
Node(int x) : s(x) {}
Node(Node* left, Node* right) : left(left), right(right) { s=left->s+right->s; }
Node* upd(int i, int l, int r) {
if (l>i||r<i) return this;
if (l==r) return new Node(s+1);
int mid=(l+r)/2;
return new Node(left->upd(i, l, mid), right->upd(i, mid+1, r));
}
int qry(int ql, int qr, int l, int r) {
if (l>qr||r<ql) return 0;
if (ql<=l&&r<=qr) return s;
int mid=(l+r)/2;
return left->qry(ql, qr, l, mid)+right->qry(ql, qr, mid+1, r);
}
};
vector<Node*> pv, pre, pce, pf; // prefix vertex, prefix row edge, prefix column edge, prefix face
void init(int R, int C, int sr, int sc, int M, char *S) {
n=R, m=C, --sr, --sc;
consider(sr, sc);
for (int i=0; i<M; ++i) {
if (S[i]=='N'||S[i]=='S') sr+=S[i]=='S'?1:-1;
else sc+=S[i]=='E'?1:-1;
assert(0<=sr&&sr<n&&0<=sc&&sc<m);
consider(sr, sc);
}
Node* cur=new Node(0, m-1);
pv.push_back(cur);
pre.push_back(cur);
pce.push_back(cur);
pf.push_back(cur);
for (int i=0; i<n; ++i) {
cur=pv.back();
for (int j : vis[i]) cur=cur->upd(j, 0, m-1);
pv.push_back(cur);
cur=pre.back();
for (int j : row_edge[i]) cur=cur->upd(j, 0, m-1);
pre.push_back(cur);
cur=pce.back();
for (int j : col_edge[i]) cur=cur->upd(j, 0, m-1);
pce.push_back(cur);
cur=pf.back();
for (int j : faces[i]) cur=cur->upd(j, 0, m-1);
pf.push_back(cur);
}
}
int cnt(vector<Node*>& p, int a, int b, int c, int d) {
return p[c+1]->qry(b, d, 0, m-1)-p[a]->qry(b, d, 0, m-1);
}
int colour(int ar, int ac, int br, int bc) {
--ar, --ac, --br, --bc;
ll v=(ll)(br-ar+1)*(bc-ac+1)-cnt(pv, ar, ac, br, bc);
ll e=(ll)(br-ar+1)*(bc-ac)+(ll)(br-ar)*(bc-ac+1)-cnt(pre, ar, ac, br, bc-1)-cnt(pce, ar, ac, br-1, bc);
ll f=(ll)(br-ar)*(bc-ac)-cnt(pf, ar, ac, br-1, bc-1)+(ar<lr&&rr<br&&ac<lc&&rc<bc);
return v-e+f;
}
/*int main() {
ios::sync_with_stdio(0);
cin.tie(0);
init(6, 4, 3, 3, 9, "NWESSWEWS");
cout << colour(2, 3, 2, 3) << " " << colour(3, 2, 4, 4) << " " << colour(5, 3, 6, 4) << " " << colour(1, 2, 5, 3) << endl;
return 0;
}*/
