Ma trận kích thước ~M~ hàng, ~N~ cột biểu diễn trạng thái các ô, ~1~-ô tốt, ~0~-ô hỏng.

Ta sửa ma trận bằng cách đặt các khối thẳng đứng vào các vùng hỏng. Các khối có thể sử dụng có độ rộng ~1~ và chiều cao có thể là ~\{1, 2, \dots, M\}~. Cần xác định số khối từng loại sao cho số lượng khối là ít nhất.

Input

• Dòng đầu là hai số ~M~ và ~N~ ~(1 \le~ ~M~, ~N \le~ ~200)~.
• ~M~ dòng sau đó gồm ~N~ kí tự ~1~ hoặc ~0~.

Output

Gọi ~C_k~ là số khối có chiều cao ~k~ cần sử dụng. In ra một số dòng theo dạng ~k~ ~C_k~ theo thứ tự tăng dần của ~k~, với ~k \in \{1, 2, \dots, M\}~ và ~C_k \neq 0~.

Sample Input

5 10 
1110000111
1100001111
1000000011
1111101111
1110000111

Sample Output

1 7
2 1
3 2
5 1