#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& is, pair<X,Y> &pr){return is>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr){return os<<pr.first<<" "<<pr.second;}
template<typename T> istream& operator>>(istream& is, vector<T> &arr){for (auto &it : arr) is>>it; return is;}
template<typename T> ostream& operator<<(ostream& os, vector<T> arr){for (auto &it : arr) os<<it<<" "; return os;}
template<typename T,size_t Y> istream& operator>>(istream& is, array<T,Y> &arr){for (auto &it : arr) is>>it; return is;}
template<typename T,size_t Y> ostream& operator<<(ostream& os, array<T,Y> arr){for (auto &it : arr) os<<it<<" "; return os;}
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it :x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define tol(bi) (1LL<<((int)(bi)))
typedef long long ll;
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "rect.h"
struct AHMET23{
vector<vector<int>> arr;
int n,m;
AHMET23(int _n, int _m):n(_n),m(_m){
arr.resize(_n,vector<int>(_m,1));
}
void update(int x, int y){
arr[x][y]=0;
}
int findup(int x, int y){
while (x>=0 && !arr[x][y])x--;
return x+1;
}
int finddown(int x, int y){
while (x<n && !arr[x][y])x++;
return x-1;
}
int findnext(int x, int y){
while (y<m && !arr[x][y])y++;
return y-1;
}
int findprev(int x, int y){
while (y>=0 && !arr[x][y])y--;
return y+1;
}
int query(int xl, int xr, int yl, int yr){
int rval = 0;
for (int x = xl; x <= xr; x++){
for (int y = yl; y <= yr; y++){
rval+=arr[x][y];
}
}
return rval;
}
void print(){
for (int i = 0; i < n; i++){
cout<<arr[i]<<endl;
}
}
};
long long count_rectangles(vector<vector<int>> arr) {
vector<pair<int,pair<int,int>>> vals;
int n = arr.size();
int m = arr[0].size();
AHMET23 ds(n,m);
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if (!arr[i][j]) ds.update(i,j);
}
}
ll ans = 0;
function<bool(int xl, int xr, int yl, int yr)> checkvalid = [&](int xl, int xr, int yl, int yr)->bool{
if (xl==0 || xr==n-1) return false;
if (yl==0 || yr==m-1) return false;
if (ds.query(xl,xr,yl,yr)!=0) return false;
if (ds.query(xl,xr,yl-1,yr+1)!=2*(xr-xl+1)) return false;
if (ds.query(xl-1,xr+1,yl,yr)!=2*(yr-yl+1)) return false;
return true;
};
set<array<int,4>> st;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
int xl = ds.findup(i,j);
int xr = ds.finddown(i,j);
int yl = ds.findprev(i,j);
int yr = ds.findnext(i,j);
if (st.find({xl,xr,yl,yr})!=st.end()) continue;
st.insert({xl,xr,yl,yr});
if (checkvalid(xl,xr,yl,yr)) ans++;
}
}
return ans;
}
