#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
// -------------------- Typedefs -------------------- //
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
// -------------------- Defines -------------------- //
#define pr pair
#define mpr make_pair
#define ff first
#define ss second
#define mset multiset
#define mmap multimap
#define uset unordered_set
#define umap unordered_map
#define umset unordered_multiset
#define ummap unordered_multimap
#define pqueue priority_queue
#define sz(x) (int((x).size()))
#define len(x) (int((x).length()))
#define all(x) (x).begin(), (x).end()
#define clr(x) (x).clear()
#define ft front
#define bk back
#define pf push_front
#define pb push_back
#define popf pop_front
#define popb pop_back
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
// -------------------- Constants -------------------- //
const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18 + 5);
const ll MOD = ll(1e9 + 7);
const ll MOD2 = ll(998244353);
// -------------------- Solution -------------------- //
const int N = 2505, M = 2505, LG = 13;
int a[N][M];
short ul[N][M], ur[N][M], uu[N][M], ud[N][M];
short hl[N][M], hr[N][M], hu[N][M], hd[N][M];
int n, m, lgn, lgm;
pr<short, short> h[N];
pr<short, short> th[N][M][LG], tv[M][N][LG];
ll e[N * M];
int ind;
void bld()
{
int i, j, k;
int g;
h[1] = mpr(0, 1);
for (i = 2; i <= 2503; i++) {
h[i] = h[i - 1];
if (h[i].ss * 2 <= i) {
h[i].ff++;
h[i].ss *= 2;
}
}
while ((1 << lgn) <= n) lgn++;
lgn--;
while ((1 << lgm) <= m) lgm++;
lgm--;
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) th[i][j][0] = mpr(hu[i][j], hd[i][j]);
g = 1;
for (k = 1; k <= lgm; k++) {
for (j = 1; j <= m - 2 * g + 1; j++) {
th[i][j][k].ff = max(th[i][j][k - 1].ff, th[i][j + g][k - 1].ff);
th[i][j][k].ss = min(th[i][j][k - 1].ss, th[i][j + g][k - 1].ss);
}
g *= 2;
}
}
for (j = 1; j <= m; j++) {
for (i = 1; i <= n; i++) tv[j][i][0] = mpr(hl[i][j], hr[i][j]);
g = 1;
for (k = 1; k <= lgn; k++) {
for (i = 1; i <= n - 2 * g + 1; i++) {
tv[j][i][k].ff = max(tv[j][i][k - 1].ff, tv[j][i + g][k - 1].ff);
tv[j][i][k].ss = min(tv[j][i][k - 1].ss, tv[j][i + g][k - 1].ss);
}
g *= 2;
}
}
return;
}
pr<int, int> qryh(int i, int l, int r)
{
int len = r - l + 1;
pr<int, int> res;
res.ff = max(th[i][l][h[len].ff].ff, th[i][r - h[len].ss + 1][h[len].ff].ff);
res.ss = min(th[i][l][h[len].ff].ss, th[i][r - h[len].ss + 1][h[len].ff].ss);
return res;
}
pr<int, int> qryv(int j, int l, int r)
{
int len = r - l + 1;
pr<int, int> res;
res.ff = max(tv[j][l][h[len].ff].ff, tv[j][r - h[len].ss + 1][h[len].ff].ff);
res.ss = min(tv[j][l][h[len].ff].ss, tv[j][r - h[len].ss + 1][h[len].ff].ss);
return res;
}
ll count_rectangles(vector<vector<int>> a0)
{
int i, j;
n = sz(a0); m = sz(a0[0]);
for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) a[i][j] = ++a0[i - 1][j - 1];
if (n < 3 || m < 3) return 0;
// closest biggers
stack<pr<int, int>> st;
for (i = 1; i <= n; i++) {
while (!st.empty()) st.pop();
for (j = 1; j <= m; j++) {
while (!st.empty() && st.top().ff <= a[i][j]) st.pop();
if (!st.empty()) ul[i][j] = st.top().ss;
st.push(mpr(a[i][j], j));
}
while (!st.empty()) st.pop();
for (j = m; j >= 1; j--) {
while (!st.empty() && st.top().ff <= a[i][j]) st.pop();
if (!st.empty()) ur[i][j] = st.top().ss;
else ur[i][j] = m + 1;
st.push(mpr(a[i][j], j));
}
}
for (j = 1; j <= m; j++) {
while (!st.empty()) st.pop();
for (i = 1; i <= n; i++) {
while (!st.empty() && st.top().ff <= a[i][j]) st.pop();
if (!st.empty()) uu[i][j] = st.top().ss;
st.push(mpr(a[i][j], i));
}
while (!st.empty()) st.pop();
for (i = n; i >= 1; i--) {
while (!st.empty() && st.top().ff <= a[i][j]) st.pop();
if (!st.empty()) ud[i][j] = st.top().ss;
else ud[i][j] = n + 1;
st.push(mpr(a[i][j], i));
}
}
// closest overlappings
for (i = 1; i <= n; i++) {
while (!st.empty()) st.pop();
for (j = 3; j <= m; j++) {
st.push(mpr(j - 1, ur[i][j - 1]));
while (!st.empty() && st.top().ss <= j) st.pop();
if (st.empty()) hl[i][j] = 0;
else hl[i][j] = st.top().ff;
}
while (!st.empty()) st.pop();
for (j = m - 2; j >= 1; j--) {
st.push(mpr(ul[i][j + 1], j + 1));
while (!st.empty() && st.top().ff >= j) st.pop();
if (st.empty()) hr[i][j] = m + 1;
else hr[i][j] = st.top().ss;
}
}
for (j = 1; j <= m; j++) {
while (!st.empty()) st.pop();
for (i = 3; i <= n; i++) {
st.push(mpr(i - 1, ud[i - 1][j]));
while (!st.empty() && st.top().ss <= i) st.pop();
if (st.empty()) hu[i][j] = 0;
else hu[i][j] = st.top().ff;
}
while (!st.empty()) st.pop();
for (i = n - 2; i >= 1; i--) {
st.push(mpr(uu[i + 1][j], i + 1));
while (!st.empty() && st.top().ff >= i) st.pop();
if (st.empty()) hd[i][j] = n + 1;
else hd[i][j] = st.top().ss;
}
}
bld();
int li, ri, lj, rj;
for (i = 2; i < n; i++) {
for (j = 2; j < m; j++) {
li = uu[i][j]; ri = ud[i][j];
lj = ul[i][j]; rj = ur[i][j];
if (li <= 0 || ri >= n + 1 || lj <= 0 || rj >= m + 1) continue;
if (qryh(li, lj + 1, rj - 1).ss < ri) continue;
if (qryh(ri, lj + 1, rj - 1).ff > li) continue;
if (qryv(lj, li + 1, ri - 1).ss < rj) continue;
if (qryv(rj, li + 1, ri - 1).ff > lj) continue;
e[++ind] = 1LL + (1LL * li) + (2500LL * ri) + (2500LL * 2500LL * lj) + (2500LL * 2500LL * 2500LL * rj);
}
}
int ans = 0;
sort(e + 1, e + ind + 1);
for (i = 1; i <= ind; i++) ans += (e[i - 1] != e[i]);
return ans;
}
/*
# # # # # # # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # #
# # # # # # # # # # # #
# # # # # # # # # # # # # #
*/
