Rectangles area

Let us consider a 2D array filled with 0's and 1's. The array may be percepted as a rectangular grid of cells, made of rows and columns, all cells being the same size.
Each cell in the array is specified by its two coordinates, also called indices.
The y-coordinate of the cell is its row coordinate/index.
The x-coordinate of the cell is its column coordinate/index.
Typically, row indices grow from top to bottom, the topmost row has index 0, the next row has index 1, etc.
Column indices grow from left to right, the leftmost column has index 0, the next column has index 1, etc.

Let us consider a 2D array with M rows and N columns.
Each integer four-tuple (x1, y1, x2, y2), where 0 ≤ x1, x2 < N, 0 ≤ y1,y2 < M, specifies a rectangle in the array. The pair (x1, y1) specifies the coordinates of one of the corners of the rectangle and the pair (x2, y2) specifies the coordinates of the opposite corner of the rectangle.

Let (x1, y1, x2, y2) specify some rectangle in a 2D array.
The border of the rectangle is an area in the array which consists of all of the following cells:
   1. Cells which y-coordinate is either y1 or y2 and which x-coordinate lies strictly between x1 and x2.
   2. Cells which x-coordinate is either x1 or x2 and which y-coordinate lies strictly between y1 and y2.
   3. Cells which x-coordinate is either x1 or x2 and which y-coordinate is either y1 or y2.
The rectangle interior is the set of all cells which y-coordinate lies strictly between y1 and y2 and which x-coordinate lies strictly between x1 and x2.
The rectangle interior size is equal to the number of cells in the rectangle interior.

A rectangle is correctly drawn if all cells in its interior are filled with 0's, all cells in its border are filled with 1's, and also all cells which are outside the border and are horizontally or vertically or diagonally immediately adjacent to the cells of the rectangle border are filled with 0's.
Note that the border of a correctly drawn rectangle may partially coincide with the first or last row/column of the array.

An experimental software started with an array filled with 0's. Then it inserted, one by one, some correctly drawn rectangles into the array. The rectangles were at different positions and had different sizes. Some of the earlier inserted rectangles became partially or completely overwriten by some of the rectangles inserted later. These overwritten rectangles are no more correctly drawn in the array.



Image 1. Examples of arrays filled with some rectangles. Blue squares represent cells with 1's, white rectangles represent cells with 0's.
a) At least 7 rectangles labeled a - g were inserted into the array. The rectangles labeled a, b, and d were partially overwritten an are not correctly drawn. The rectangles labeled c, e, f, g are correctly drawn. It is obvious that the rectangle labeled c was inserted later than the rectangle labeled b and this rectangle was inserted later than the rectangles labeled d and a.
b) At least 6 rectangles labeled a - f were inserted into the array. The rectangles labeled a, c and d were partially overwritten an are not correctly drawn. The rectangles labeled b, e and f are correctly drawn.
c) At least 5 rectangles labeled a - e were inserted into the array. The rectangles labeled a, b, and c were partially overwritten an are not correctly drawn. The rectangles labeled d and e are correctly drawn. It is obvious that the rectangle labeled d was inserted later than the rectangle labeled c and this rectangle was inserted later than the rectangle labeled b and and this rectangle was inserted later than the rectangle labeled a.
Note that the labels are used only to identify the rectangles in the picture, they do not appear in the input data.

The task

A 2D array of 0's and 1's is given. The array was filed with a sequence of correctly drawn rectangles of various sizes on different positions. Count the number of the remaining correctly drawn rectangles in the array and calculate the total area of their interiors.

Input

The first input line contains two integer M and N separated by space and specifying the number of rows and the number of columns in a 2D array which is on the next M lines. Each of next M lines contains N values which specify the contents of a row in the array, the values are separated by spaces. Each value is 0 or 1.
It holds 5 ≤ M, N ≤ 1000.

Output

The output contains one text line with two integers separated by space. The first integer represents the number of correctly drawn rectangles in the input array. The second line represents the sum of areas of interiors of all correctly drawn retangles in the input array.

Example 1

Input
13 21
1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 1 1 0 0
1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 0
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0
0 1 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 0 0
0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 1 1
0 1 0 0 1 1 1 0 0 1 0 0 0 0 1 0 0 1 0 0 1
0 1 0 0 1 0 1 0 1 1 0 0 0 0 1 0 0 1 0 0 1
0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1
0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Output
4 10

Example 2

Input
17 4
1 1 1 1
1 0 0 1
1 1 1 1
0 0 0 0
1 1 1 1
1 0 0 1
1 1 1 1
0 0 0 0
1 1 1 1
0 0 0 0
1 1 1 1
1 0 0 1
1 1 1 1
0 0 0 0
1 1 1 0
0 0 0 0
1 1 1 1
Output
3 6

Example 3

Input
13 9
0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 1
0 0 0 0 1 1 1 0 1
0 0 0 0 0 0 1 0 1
0 0 1 1 1 0 1 0 0
0 0 0 0 1 0 1 0 0
1 1 1 0 1 0 0 0 0
1 0 1 0 1 0 0 0 0
1 0 1 0 0 0 0 0 0
1 0 1 0 1 1 1 1 1
1 0 1 0 1 0 0 0 1
1 0 1 0 1 1 1 1 1
1 1 1 0 0 0 0 0 0
Output
2 8

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set