Problem: Offering the ABBYY Cup participants a problem written by the Smart Beaver is becoming a tradition. He proposed the following problem.

You are given a monochrome image, that is, an image that is composed of two colors (black and white). The image is given in raster form, that is, as a matrix of pixels' colors, and the matrix's size coincides with the size of the image.

The white color on the given image corresponds to the background. Also, the image contains several black geometric shapes. It is known that the image can contain only two types of shapes: squares and circles. Your task is to count the number of circles and the number of squares which the given image contains.

The squares on the image can be rotated arbitrarily. In addition, the image can possibly contain some noise arranged as follows: each pixel of the original image can change its color to the opposite with the probability of 20%.

<image> An example of an image that has no noise and the sides of the squares are parallel to the coordinate axes (two circles and three squares).  <image> An example of an image that has no noise and the squares are rotated arbitrarily (two circles and three squares).  <image> An example of an image that has noise and the squares are rotated arbitrarily (one circle and three squares). 

Input

The first input line contains a single integer n (1000 ≤ n ≤ 2000), which is the length and the width of the original image. 

Next n lines describe the matrix of colors of the image pixels. The i-th line contains exactly n integers aij (0 ≤ aij ≤ 1), separated by spaces. Value of aij = 0 corresponds to a white pixel and aij = 1 corresponds to a black one. 

It is guaranteed that the lengths of the sides of the squares and the diameters of the circles in the image are at least 15 pixels, and the distance between any two figures is at least 10 pixels. It is also guaranteed that a human can easily calculate the number of circles and squares in the original image. The total number of figures in the image doesn't exceed 50.

The input limitations for getting 20 points are: 

  * These test cases have no noise and the sides of the squares are parallel to the coordinate axes. 



The input limitations for getting 50 points are: 

  * These test cases have no noise, but the squares are rotated arbitrarily. 



The input limitations for getting 100 points are: 

  * These test cases have noise and the squares are rotated arbitrarily. 

Output

Print exactly two integers, separated by a single space — the number of circles and the number of squares in the given image, correspondingly.

Examples

Note

You are given a sample of original data for each difficulty level. The samples are available at http://codeforces.ru/static/materials/contests/178/e-samples.zip .

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:200000000")
const double EPS = 1E-9;
const int INF = 1000000000;
const long long INF64 = (long long)1E18;
const double PI = 3.1415926535897932384626433832795;
const double EPS_ANG = 1E-13;
const double MAGIC = 90;
const int NOIZE = 110;
const int ITER = 0;
const int DIRS = 8;
const int NEIGHBOURS = DIRS;
const int dx[8] = {-1, 0, +1, 0, -1, -1, +1, +1};
const int dy[8] = {0, +1, 0, -1, -1, +1, -1, +1};
struct pt {
  int x, y;
  pt() {}
  pt(int x, int y) : x(x), y(y) {}
};
inline bool operator<(const pt &a, const pt &b) {
  return make_pair(a.x, a.y) < make_pair(b.x, b.y);
}
vector<pt> cur;
bool u[2100][2100];
int a[2100][2100], n, s;
inline bool isin(int x, int y) { return 0 <= x && x < n && 0 <= y && y < n; }
inline long long vec(pt a, pt b, pt c) {
  return long long(b.x - a.x) * (c.y - a.y) -
         long long(b.y - a.y) * (c.x - a.x);
}
pt glc;
inline long long dist(pt a, pt b) {
  return (a.x - b.x) * long long(a.x - b.x) +
         (a.y - b.y) * long long(a.y - b.y);
}
bool cmp_ang(const pt &a, const pt &b) {
  double a1 = atan2((double)a.y - glc.y, a.x - glc.x);
  double a2 = atan2((double)b.y - glc.y, b.x - glc.x);
  return a1 < a2 - EPS_ANG ||
         abs(a1 - a2) < EPS_ANG && dist(glc, a) < dist(glc, b);
}
inline int sign(long long a) { return a == 0 ? 0 : a > 0 ? +1 : -1; }
vector<pt> convex_hull(vector<pt> &a) {
  if (a.size() <= 2) return a;
  swap(a[0], *min_element(a.begin(), a.end()));
  glc = a[0];
  sort(a.begin() + 1, a.end(), cmp_ang);
  vector<pt> v;
  v.reserve(a.size());
  v.push_back(a[0]);
  v.push_back(a[1]);
  for (int i = (int)(2); i < (int)(a.size()); i++) {
    while (v.size() > 1 && sign(vec(v[v.size() - 2], v.back(), a[i])) <= 0)
      v.pop_back();
    v.push_back(a[i]);
  }
  return v;
}
void dfs(int x, int y) {
  u[x][y] = true;
  s++;
  bool hack = false;
  for (int dir = 0; dir < (int)(DIRS); dir++) {
    int nx = x + dx[dir];
    int ny = y + dy[dir];
    if (!isin(nx, ny) || a[nx][ny] == 0) {
      hack = true;
      continue;
    }
    if (u[nx][ny]) continue;
    dfs(nx, ny);
  }
  if (hack) cur.push_back(pt(x, y));
}
double mass_hacks(vector<pt> a) {
  double cx = 0, cy = 0;
  for (int i = 0; i < (int)(a.size()); i++) {
    cx += a[i].x;
    cy += a[i].y;
  }
  cx /= a.size();
  cy /= a.size();
  double mi = 1E20;
  double ma = -1E20;
  for (int i = 0; i < (int)(a.size()); i++) {
    double di =
        sqrt((a[i].x - cx) * (a[i].x - cx) + (a[i].y - cy) * (a[i].y - cy));
    mi = min(mi, di);
    ma = max(ma, di);
  }
  double sum = 0;
  for (int i = 0; i < (int)(a.size()); i++) {
    double di =
        sqrt((a[i].x - cx) * (a[i].x - cx) + (a[i].y - cy) * (a[i].y - cy));
    sum += (ma - di) * (ma - di);
    sum += (di - mi) * (di - mi);
  }
  sum /= a.size();
  return ma / mi;
}
double get_rad(vector<pt> a) {
  double cx = 0, cy = 0;
  for (int i = 0; i < (int)(a.size()); i++) {
    cx += a[i].x;
    cy += a[i].y;
  }
  cx /= a.size();
  cy /= a.size();
  double mi = 1E20;
  double ma = -1E20;
  double sum = 0;
  for (int i = 0; i < (int)(a.size()); i++) {
    double di =
        sqrt((a[i].x - cx) * (a[i].x - cx) + (a[i].y - cy) * (a[i].y - cy));
    mi = min(mi, di);
    ma = max(ma, di);
    sum += di;
  }
  return sum / a.size();
}
double get_side1(vector<pt> a) {
  double cx = 0, cy = 0;
  for (int i = 0; i < (int)(a.size()); i++) {
    cx += a[i].x;
    cy += a[i].y;
  }
  cx /= a.size();
  cy /= a.size();
  double mi = 1E20;
  double ma = -1E20;
  double sum = 0;
  for (int i = 0; i < (int)(a.size()); i++) {
    double di =
        sqrt((a[i].x - cx) * (a[i].x - cx) + (a[i].y - cy) * (a[i].y - cy));
    mi = min(mi, di);
    ma = max(ma, di);
    sum += di;
  }
  return mi * 2;
}
double get_side2(vector<pt> a) {
  double cx = 0, cy = 0;
  for (int i = 0; i < (int)(a.size()); i++) {
    cx += a[i].x;
    cy += a[i].y;
  }
  cx /= a.size();
  cy /= a.size();
  double mi = 1E20;
  double ma = -1E20;
  double sum = 0;
  for (int i = 0; i < (int)(a.size()); i++) {
    double di =
        sqrt((a[i].x - cx) * (a[i].x - cx) + (a[i].y - cy) * (a[i].y - cy));
    mi = min(mi, di);
    ma = max(ma, di);
    sum += di;
  }
  return ma / sqrt(2.0) * 2;
}
int main() {
  cin >> n;
  for (int i = 0; i < (int)(n); i++)
    for (int j = 0; j < (int)(n); j++) scanf("%d", &a[i][j]);
  for (int ii = 0; ii < (int)(ITER); ii++) {
    bool br = true;
    for (int x = 0; x < (int)(n); x++)
      for (int y = 0; y < (int)(n); y++) {
        int cnt = 0;
        for (int dir = 0; dir < (int)(DIRS); dir++) {
          int nx = x + dx[dir];
          int ny = y + dy[dir];
          if (isin(nx, ny) && a[nx][ny] != a[x][y]) cnt++;
        }
        if (cnt >= NEIGHBOURS) {
          a[x][y] ^= 1;
          br = false;
        }
      }
    if (!br) break;
  }
  int c1 = 0, c2 = 0;
  for (int i = 0; i < (int)(n); i++)
    for (int j = 0; j < (int)(n); j++)
      if (a[i][j] == 1 && !u[i][j]) {
        cur.clear();
        s = 0;
        dfs(i, j);
        if (s <= NOIZE && cur.size() <= NOIZE) continue;
        cur = convex_hull(cur);
        double di = mass_hacks(cur);
        double r = get_rad(cur);
        double exp_c2 = PI * r * r * 0.8;
        double side1 = get_side1(cur);
        double exp_c11 = side1 * side1 * 0.8;
        double side2 = get_side2(cur);
        double exp_c12 = side2 * side2 * 0.8;
        double perc = s / exp_c2;
        cerr << perc << endl;
        if (perc > 0.85)
          c2++;
        else
          c1++;
      }
  cout << c2 << ' ' << c1 << endl;
  return 0;
}