Cho một ma trận A kích thước MxN, các phần tử A[i,j] bằng 0 hoặc bằng 1, các ô số 1 liền cạnh nhau khép kín có thể tạo thành hình chữ nhật đậm đặc – toàn là số 1 hoặc hình chữ nhật bị rỗng ở trong (ở trong lòng hình chữ nhật có các số 0).

Yêu cầu:

Hãy đếm xem có bao nhiêu hình chữ nhật như trên, trong đó có bao nhiêu hình chữ nhật đậm đặc (loại 1) và bao nhiêu hình chữ nhật rỗng ở trong có duy nhất một hình chữ nhật chứa toàn số 0 (loại 2)?

Dữ liệu:

Dòng đầu chứa 2 số M, N (1 < M, N <= 200)
M dòng tiếp theo thể hiện ma trận A. (mỗi số cách nhau một dấu cách)

Kết quả:

• Dòng đầu chứa số lượng các loại hình chữ nhật
• Dòng thứ hai chứa số lượng các hình chữ nhật loại 1
• Dòng thứ ba chứa số lượng các hình chữ nhật loại 2.

Input

10 10
1 1 0 0 0 1 0 0 0 0
1 1 0 1 1 1 0 0 0 0
0 0 0 0 0 0 1 1 0 0
0 0 1 1 1 1 0 0 0 0
0 0 1 0 0 1 0 0 0 0
0 0 1 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 1 1 1 1 1 1 0
0 0 0 1 0 1 1 0 1 0
0 0 0 1 1 1 1 1 1 0

Output

5
3
1

Ràng buộc:

• Có 30% số test ứng với 30% số điểm của bài có 1 < M, N <= 50.
• Có 30% số test ứng với 30% số điểm của bài có 50 < M, N <= 100.
• Có 40% số test ứng với 40% số điểm của bài có 100 < M, N <= 200.