Cooperating Robot Pairs

In this problem, we consider a flat rectangular field consisting of M×N cells.
Each cell is either empty or there is an experimental robot standing in the cell or there is large cardboard box covering the entire cell. The cells with the boxes are called obstruction cells. There is at most one robot in any cell.

A pair of robots (R1, R2) is called a cooperation pair if R1 and R2 stand in the same row or in the same column and all cells in that row/column between R1 and R2 are empty.
A cooperation degree of a robot is the number of cooperation pairs of which the robot is a member. Note that the maximum cooperation degree of a robot is 4.
A cooperation degree of a cooperation pair is the sum of the cooperation degrees of its (two) members. Note that the cooperation degree of any cooperation pair is at least 2 and at most 8.



Image 1. The left image depicts a field with some robots and obstruction cells. The cells with robots are marked by R and are highlighted in blue, the obstruction cells are marked by X and are highlighted in red.
The right image depicts the cooperation pairs of the robots in the field in the left image. The robots are depicted as blue circles. Each cooperation pair is depicted as a straight line between the corresponding robots and it is labeled by the cooperation degree of the cooperation pair. Both images illustrate Example 1 below.

The task

Determine the number of cooperating pairs for each possible cooperation degree of a cooperating pair.

Input

The first input line contains two integers M and N representing the number of rows and the number of columns of the input field. Next, there are exactly M lines. Each line contains N values, the values correspond to the values in a particular row in the field. Each value is 0 or 1 or 2. Value 0 represents empty cell, value 1 represents a cell with a robot and value 2 represents an obstruction cell. All values are separated by single space.
It holds 2 ≤ M, N ≤ 1000.

Output

The output contains 7 text lines. Each line contains two integers k, m(k), separated by space. Value k represents the cooperation degree of a cooperation pair, value m(k) represents the number of cooperation pairs which cooperation degree is equal to k. The lines are listed in ascending order of k. The value of k on the first output line is 2, the value of k on the last output line is 8.

Example 1

Input
5 15
1 2 1 0 0 0 0 1 0 0 1 0 0 0 0
0 2 2 0 1 0 0 0 0 2 0 0 0 0 0
0 0 1 0 1 0 0 1 0 0 0 0 1 0 1
1 0 0 0 0 0 2 0 0 1 0 1 0 0 0
0 1 2 0 1 0 0 1 0 0 0 0 0 0 0
Output
2 2
3 1
4 3
5 2
6 3
7 1
8 1

Example 2

Input
6 5
0 0 1 1 1
0 0 1 1 1
2 2 1 1 1
2 2 1 1 1
1 1 2 2 0
1 1 2 2 0
Output
2 0
3 0
4 4
5 8
6 2
7 6
8 1

Example 3

Input
9 9
1 0 1 0 1 0 1 0 1
2 2 0 0 0 0 0 0 0
1 0 1 0 1 0 1 0 1
0 0 2 2 0 0 0 0 0
1 0 1 0 1 0 1 0 1
0 0 0 0 2 2 0 0 0
1 0 1 0 1 0 1 0 1
0 0 0 0 0 0 2 2 0
1 0 1 0 1 0 1 0 1
Output
2 0
3 0
4 2
5 8
6 12
7 12
8 2

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