Giống như mọi cô bò khác, Bessie thích giải ô chữ. Không may, cô em Elsie đã làm đổ sữa lên khắp cuốn sách ô chữ của Bessie, khiến chữ bị nhòe và Bessie khó nhìn ra vị trí bắt đầu của mỗi gợi ý. Nhiệm vụ của bạn là giúp Bessie khôi phục cách đánh số các gợi ý!

Bạn được cho một ô chữ chưa đánh số dưới dạng lưới \(N\) hàng và \(M\) cột (\(3 \le N \le 50\), \(3 \le M \le 50\)). Một số ô là ô trống (thường có màu trắng), còn một số ô bị chặn (thường có màu đen). Với bố cục này, việc đánh số gợi ý là một quy trình đơn giản gồm hai bước logic:

Bước 1: Xác định mỗi ô có bắt đầu một gợi ý theo chiều ngang hoặc chiều dọc hay không. Nếu một ô bắt đầu một gợi ý theo chiều ngang, ô đó phải là ô trống, ô ngay bên trái phải bị chặn hoặc nằm ngoài lưới ô chữ, và hai ô bên phải phải là ô trống (nghĩa là một gợi ý theo chiều ngang chỉ có thể biểu diễn một từ gồm ít nhất 3 ký tự). Quy tắc đối với một ô bắt đầu gợi ý theo chiều dọc cũng tương tự: ô phía trên phải bị chặn hoặc nằm ngoài lưới, và hai ô phía dưới phải là ô trống.

Bước 2: Gán số cho mỗi ô bắt đầu một gợi ý. Các ô được gán các số liên tiếp bắt đầu từ 1, theo đúng thứ tự đọc sách: các ô ở hàng trên cùng được gán số từ trái sang phải, sau đó đến hàng thứ hai, v.v. Chỉ những ô bắt đầu một gợi ý mới được gán số.

Ví dụ, xét lưới sau, trong đó . biểu thị một ô trống và # biểu thị một ô bị chặn.

...
#..
...
..#
.##

Các ô có thể bắt đầu một gợi ý theo chiều ngang hoặc chiều dọc được đánh dấu bằng ! dưới đây:

!!!
#..
!..
..#
.##

Nếu gán số cho các ô này, ta được:

123
#..
4..
..#
.##

Lưu ý rằng ô chữ được mô tả trong dữ liệu vào có thể không thỏa mãn những điều kiện thường thấy ở các ô chữ đã xuất bản. Chẳng hạn, một số ô trống có thể không thuộc bất kỳ gợi ý nào.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\), cách nhau bởi một dấu cách.

\(N\) dòng tiếp theo, mỗi dòng mô tả một hàng của lưới và chứa \(M\) ký tự. Mỗi ký tự là . (một ô trống) hoặc # (một ô bị chặn).

Dữ liệu ra

Trên dòng đầu tiên, in ra số lượng gợi ý.

Trên mỗi dòng còn lại, in ra hàng và cột xác định vị trí của một gợi ý, theo thứ tự đã mô tả ở trên. Ô trên cùng bên trái có vị trí \((1,1)\). Ô dưới cùng bên phải có vị trí \((N,M)\).

Ví dụ

5 3
...
#..
...
..#
.##

4
1 1
1 2
1 3
3 1

Nguồn

USACO 2014 December Contest, Bronze — Crosswords. Tác giả đề: Mark Gordon, 2014.

https://usaco.org/index.php?page=viewproblem2&cpid=488