// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define pb push_back
#ifndef safar
#include "rainbow.h"
#endif
using namespace std;
const int N = 2e5 + 10;
typedef pair<int, int> pii;
template<typename T>
void Unique(vector<T> &V){
sort(all(V));
V.resize(unique(all(V)) - V.begin());
}
int R, C;
vector<pii> Riv, P;
pii corner[] = {{0, 0}, {0, -1}, {-1, -1}, {-1, 0}};
bool Exist(pii X){
return X == *lower_bound(all(Riv), X);
}
vector<int> RE[N], CE[N];
vector<pii> Fen[N];
vector<int> PS[N];
void Add(pii P, int d){
//cerr << "# " << P.F << " " << P.S << " : " << d << '\n';
for(int idx = P.F; idx < N; idx += idx & (-idx))
Fen[idx].pb({P.S, d});
}
////////////////
int com;
const int N2 = 3*N;
vector<pii> Fr;
int mark[N2];
int ID(pii X){
int x = lower_bound(all(Fr), X) - Fr.begin();
if(x == (int)Fr.size()) return -1;
if(Fr[x] != X) return -1;
return x;
}
pii side[] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
void DFS(int u){
int X = Fr[u].F;
int Y = Fr[u].S;
mark[u] = 1;
int adj;
for(auto [x, y] : side){
adj = ID({X + x, Y + y});
if(adj == -1 || mark[adj]) continue;
DFS(adj);
}
}
////////////////
int mxx = -1, mxy = -1, mnx = 1e9, mny = 1e9;
void init(int Ri, int Ci, int sr, int sc, int m, char *s){
R = Ri; C = Ci;
Riv.resize(m + 1);
Riv[0] = {sr, sc};
for(int i = 1; i <= m; i++){
if(s[i - 1] == 'N') sr --;
if(s[i - 1] == 'S') sr ++;
if(s[i - 1] == 'W') sc --;
if(s[i - 1] == 'E') sc ++;
Riv[i] = {sr, sc};
}
Unique(Riv);
for(auto &X : Riv)
for(auto &del : corner)
if(min(X.F + del.F, X.S + del.S) > 0)
P.pb({X.F + del.F, X.S + del.S});
for(auto &X : Riv)
for(int x = X.F - 1; x <= X.F + 1; x++)
for(int y = X.S - 1; y <= X.S + 1; y++)
if(!Exist({x, y}))
Fr.pb({x, y});
Unique(P);
//for(auto X : Riv) cerr << X.F << ' ' << X.S << '\n';
Riv.pb({R + R, C + 2});
for(auto &X : Riv){
if(X.F == R + R) break;
for(int x = X.F - 1; x <= X.F + 1; x++)
for(int y = X.S - 1; y <= X.S + 1; y++)
if(!Exist({x, y}))
Fr.pb({x, y});
mxx = max(mxx, X.F);
mnx = min(mnx, X.F);
mxy = max(mxy, X.S);
mny = min(mny, X.S);
if(!Exist({X.F, X.S - 1}))
RE[X.F].pb(X.S - 1);
if(!Exist({X.F, X.S + 1}))
RE[X.F].pb(X.S);
if(!Exist({X.F - 1, X.S}))
CE[X.S].pb(X.F - 1);
if(!Exist({X.F + 1, X.S}))
CE[X.S].pb(X.F);
}
Unique(Fr);
for(int i = 0; i < (int) Fr.size(); i++){
if(!mark[i]){
DFS(i);
com ++;
}
}
//cerr << "## " << com << '\n';
int cnt;
vector<int> ex;
for(auto X : P){
cnt = 0;
int po = 0;
ex.clear();
for(auto &del : corner){
if(Exist({X.F - del.F, X.S - del.S})){
cnt ++;
ex.pb(po);
}
po ++;
}
if(cnt & 1)
Add(X, cnt == 1 ? -1 : 1);
if(cnt == 2){
if(ex[1] - ex[0] == 2){
Add(X, 2);
}
}
}
for(int i = 1; i < N; i++){
sort(all(Fen[i]));
PS[i].resize(Fen[i].size() + 1, 0);
for(int j = 1; j <= (int) Fen[i].size(); j++){
PS[i][j] = PS[i][j - 1] + Fen[i][j - 1].S;
}
}
}
int Get(int x, int y){
int res = 0;
for(; x; x -= x & (-x)){
res += PS[x][upper_bound(all(Fen[x]), pii(y, 5)) - Fen[x].begin()];
}
return res;
}
int colour(int ar, int ac, int br, int bc){
if((ar < mnx) && (ac < mny) && (mxx < br) && (mxy < bc)){
//assert(false);
return com;
}
int sum = 0;
if(!Exist({ar, ac})) sum ++;
if(!Exist({ar, bc})) sum ++;
if(!Exist({br, ac})) sum ++;
if(!Exist({br, bc})) sum ++;
//cerr << "1 " << sum << '\n';
if(ar < br && ac < bc){
sum += Get(br - 1, bc - 1);
//cerr << "1.1 " << sum << '\n';
sum -= Get(ar - 1, bc - 1);
sum -= Get(br - 1, ac - 1);
sum += Get(ar - 1, ac - 1);
}
//cerr << "2 " << sum << '\n';
sum += lower_bound(all(RE[ar]), bc) - upper_bound(all(RE[ar]), ac - 1);
sum += lower_bound(all(RE[br]), bc) - upper_bound(all(RE[br]), ac - 1);
sum += lower_bound(all(CE[ac]), br) - upper_bound(all(CE[ac]), ar - 1);
sum += lower_bound(all(CE[bc]), br) - upper_bound(all(CE[bc]), ar - 1);
//cerr << "! " << sum << '\n';
assert(sum % 4 == 0);
return sum / 4;
}
#ifdef safar
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
init(6, 6, 2, 2, 8, "ESNW");
//cerr << "# " << Get(6, 4) << '\n';
//cerr << Get(3, 2) << '\n';
cout << colour(1, 1, 6, 6) << '\n';
//cout << colour(3, 2, 4, 4) << '\n';
//cout << colour(5, 3, 6, 4) << '\n';
//cout << colour(1, 2, 5, 3) << '\n';
//cout << colour(1, 1, 6, 4) << '\n';
return 0;
}
#endif
