#include "rect.h"
#include "bits/stdc++.h"
#include <cstdio>
#include <unistd.h>
#include <cassert>
#include <string>
using namespace std;
int n, m;
vector<vector<pair<int, int> > > par;
vector<vector<int> > lowi, lowj, highi, highj;
vector<vector<int> > grid;
vector<vector<int> > pf;
void setup(int n, int m) {
for (int i=0; i<n; i++) {
par.push_back(vector<pair<int, int> >(m));
lowi.push_back(vector<int>(m));
lowj.push_back(vector<int>(m));
highi.push_back(vector<int>(m));
highj.push_back(vector<int>(m));
}
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
par[i][j] = make_pair(i, j);
lowi[i][j] = i;
lowj[i][j] = j;
highi[i][j] = i;
highj[i][j] = j;
}
}
}
pair<int, int> parent(pair<int, int> where) {
if (par[where.first][where.second] == where) return where;
return par[where.first][where.second] = parent(par[where.first][where.second]);
}
bool arc(pair<int, int> a, pair<int, int> b) {
return parent(a) == parent(b);
}
void connect(pair<int, int> a, pair<int, int> b) {
if (arc(a, b)) return;
pair<int, int> ax = parent(a);
pair<int, int> bx = parent(b);
par[bx.first][bx.second] = ax;
lowi[ax.first][ax.second] = min(lowi[ax.first][ax.second], lowi[bx.first][bx.second]);
lowj[ax.first][ax.second] = min(lowj[ax.first][ax.second], lowj[bx.first][bx.second]);
highi[ax.first][ax.second] = max(highi[ax.first][ax.second], highi[bx.first][bx.second]);
highj[ax.first][ax.second] = max(highj[ax.first][ax.second], highj[bx.first][bx.second]);
}
int getlowi(pair<int, int> a) {
a = parent(a);
return lowi[a.first][a.second];
}
int getlowj(pair<int, int> a) {
a = parent(a);
return lowj[a.first][a.second];
}
int gethighi(pair<int, int> a) {
a = parent(a);
return highi[a.first][a.second];
}
int gethighj(pair<int, int> a) {
a = parent(a);
return highj[a.first][a.second];
}
void dopf() {
for (int i=1; i<n; i++) {
pf[i][0] = pf[i-1][0] + grid[i][0];
}
for (int i=1; i<m; i++) {
pf[0][i] = pf[0][i-1] + grid[0][i];
}
for (int i=1; i<n; i++) {
for (int j=1; j<m; j++) {
pf[i][j] = pf[i-1][j] + pf[i][j-1] - pf[i-1][j-1] + grid[i][j];
}
}
}
int pfq(int a, int b) {
if (a < 0) return 0;
if (b < 0) return 0;
return pf[min(n-1, a)][min(m-1, b)];
}
int qpf(int a, int b, int c, int d) {
return pfq(c, d) + pfq(a-1, b-1) - pfq(c, b-1) - pfq(a-1, d);
}
long long count_rectangles(std::vector<std::vector<int> > a) {
n = a.size();
m = a[0].size();
grid = a;
pf = a;
dopf();
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (a[i][j] != 0 && a[i][j] != 1) {
int count = 0;
for (int i=1; i<n-1; i++) {
for (int j=1; j<m-1; j++) {
for (int k=i; k<n-1; k++) {
for (int l=j; l<m-1; l++) {
// check i,j to k,l
bool ok = true;
for (int x=i; x<=k && ok; x++) {
for (int y=j; y<=l && ok; y++) {
if (a[x][y] >= a[i-1][y]) ok = false;
if (a[x][y] >= a[k+1][y]) ok = false;
if (a[x][y] >= a[x][j-1]) ok = false;
if (a[x][y] >= a[x][l+1]) ok = false;
}
}
count += ok;
}
}
}
}
return count;
}
}
}
setup(n, m);
for (int i=0; i<n-1; i++) {
for (int j=0; j<m; j++) {
if (a[i][j] == 0 && a[i+1][j] == 0) {
// cout << i << ' ' << j << ' ' << i + 1 << ' ' << j << endl;
connect(make_pair(i, j), make_pair(i+1, j));
}
}
}
for (int i=0; i<n; i++) {
for (int j=0; j<m-1; j++) {
if (a[i][j] == 0 && a[i][j+1] == 0) {
// cout << i << ' ' << j << ' ' << i << ' ' << j + 1 << endl;
connect(make_pair(i, j), make_pair(i, j+1));
}
}
}
int res = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
pair<int, int> f = make_pair(i, j);
// cout << i << ':' << j << " par: " << parent(f).first << ':' << parent(f).second << " val: " << a[i][j] << endl;
if (parent(f) == f && a[i][j] == 0) {
// cout << "SEARCH" << endl;
int li = getlowi(f);
int hi = gethighi(f);
int lj = getlowj(f);
int hj = gethighj(f);
if (li == 0) continue;
if (lj == 0) continue;
if (hi == n-1) continue;
if (hj == m-1) continue;
// cout << li << ' ' << lj << ' ' << hi << ' ' << hj << endl;
// cout << " > " << i << ' ' << j << endl;
if (qpf(li, lj, hi, hj) == 0) {
// cout << " USE " << endl;
res++;
}
}
}
}
return res;
}
