Chắc hẳn các bạn đã từng nghe tới Sherlock Holmes, nhân vật thám tử hư cấu do nhà văn người Anh Conan Doyle sáng tạo nên. Sherlock Holmes đã làm say đắm biết bao tín đồ truyện trinh thám nhờ những màn phá án thần thánh với tài suy luận logic tuyệt vời cùng khả năng quan sát, diễn dịch và khoa học pháp y điêu luyện. Sherlock Homes đã được sách kỷ lục Guinness liệt kê vào danh sách nhân vật được khắc họa nhiều nhất trong văn học và điện ảnh. Danh tiếng toàn cầu của Conan Doyle gắn liền với Sherlock Homes thì ai cũng biết, nhưng nguồn gốc của tên gọi Sherlock Homes thì nhiều người chưa biết tới. Đó là bởi, nhà văn Conan Doyle có một người họ hàng xa có nghề làm khóa thông minh gia truyền. Thương hiệu khóa của người họ hàng này có tên là Sir Lock Home.

Gần đây, Sir Lock Home cho ra mắt một dòng sản phẩm khóa cửa nhà được hãng mệnh danh là "loại khóa an toàn nhất thế giới, thách thức mọi công nghệ phá khóa hiện đại nhất mọi thời đại". Đây là loại khóa số có thiết kế đặc biệt, với mật khẩu là một bảng gồm \(n\) hàng và \(m\) cột. Các hàng được đánh số từ \(1\) đến \(n\) theo thứ tự từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(m\) theo thứ tự từ trái qua phải. Để nhập mật khẩu, người dùng cần điền một chữ số từ \(0\) đến \(9\) vào mỗi ô của bảng số này.

Thông thường, bạn sẽ nghĩ để mở khóa, người dùng cần nhập chính xác cả \(n \cdot m\) chữ số của bảng mật khẩu này. Nhưng hãng khóa Sir Lock Home không nghĩ như vậy. Họ cho rằng, nếu chỉ nhập và so sánh mật khẩu theo cách thông thường, khách hàng sẽ khó giữ kín mật khẩu. Chỉ cần chủ nhân vô tình để lộ bảng số mật khẩu cho người lạ nhìn thấy, mọi chốt an toàn coi như tan biến. Do đó, cơ chế bảo mật của loại khóa này được hãng Sir Lock Home thiết kế thông minh hơn, cụ thể như sau: Khi giao khóa cho khách hàng, Sir Lock Home đưa cho khách một bảng chữ số gồm \(n\) hàng và \(m\) cột, gọi là bảng cơ sở của khóa. Nếu chỉ nhập y nguyên bảng cơ sở này, khóa (có thể) sẽ không mở. Thay vào đó, người dùng sẽ phải thay đổi chữ số ở một số ô để bảng mật khẩu thỏa mãn các tính chất sau:

• Nếu ghép \(m\) chữ số của mỗi hàng thành một con số có \(m\) chữ số trong hệ thập phân (trong đó chữ số ở cột \(1\) là chữ số lớn nhất, chữ số ở cột \(m\) là chữ số hàng đơn vị, số có thể có chữ số \(0\) ở đầu); thì \(n\) con số ở \(n\) hàng tạo thành một dãy số tăng chặt. Cụ thể, số ở hàng \(1\) nhỏ hơn số ở hàng \(2\), số ở hàng \(2\) nhỏ hơn số ở hàng \(3\), \(\ldots\), số ở hàng \(n\) là số lớn nhất.
• Số ô có chữ số bị thay đổi phải nhỏ nhất có thể.
• Nếu có nhiều cách thay đổi chữ số thỏa mãn đồng thời cả hai điều kiện trên, mọi cách như vậy đều mở được khóa.

Sir Lock Home cho rằng, mặc dù mật khẩu để mở khóa không phải duy nhất, nhưng độ khó của bài toán tìm số ô tối thiểu cần thay đổi này sẽ làm nản lòng những tên đạo trích dốt thuật toán và khiến chúng từ bỏ ý đồ xâm phạm nhà bạn.

Nhưng bạn là một người đạt huy chương vàng IOI thì sao? Liệu bạn có thể tìm ra số ô tối thiểu cần thay đổi và chỉ ra một cách bất kỳ để mở khóa hay không? Hãy cùng thử tài phá loại khóa này nhé!

Dữ liệu

Vào từ file văn bản sirlockhome.inp:

• Dòng thứ nhất chứa hai số nguyên \(n\) và \(m\) \((1 \leq n \leq 400, 1 \leq m \leq 70, n \leq 10^m)\).
• Trong \(n\) dòng còn lại, mỗi dòng chứa \(m\) chữ số từ \(0\) đến \(9\) mô tả bảng cơ sở của khóa.

Kết quả

Ghi ra file văn bản sirlockhome.out:

• Dòng thứ nhất chứa một số nguyên là số ô tối thiểu cần thay đổi.
• Trong \(n\) dòng còn lại, mỗi dòng chứa \(m\) chữ số mô tả một phương án thay đổi các ô chữ số thỏa mãn các điều kiện ở trên.

Nếu có nhiều phương án, bạn được phép đưa ra một phương án bất kỳ.

Ràng buộc

• Subtask \(1\) (\(16\) điểm): \(m \leq 3\)
• Subtask \(2\) (\(22\) điểm): \(m \leq 5\)
• Subtask \(3\) (\(28\) điểm): \(n \leq 100\)
• Subtask \(4\) (\(16\) điểm): Tất cả \(n \cdot m\) chữ số của bảng cơ sở đều giống nhau.
• Subtask \(5\) (\(18\) điểm): Không có ràng buộc gì thêm.

Với mỗi test, bạn được \(0.36\) điểm nếu tìm ra được số ô tối thiểu cần thay đổi, nhưng không tìm ra được phương án thay đổi tối ưu.

Ví dụ

8 2
22
07
19
97
19
97
07
22

6
02
07
19
67
69
77
87
92