Giải bài trực tuyến

Cho một bảng kích thước M * N. Các hàng được đánh số từ 1 đến M từ trên xuống dưới. Các cột được đánh số từ 1 đến N từ trái sang phải. Mỗi ô của bảng có giá trị là 0 hoặc 1. Bạn được thực hiện thao tác: Chọn một hình vuông 3*3 nằm trọn vẹn trong bảng và đảo bit tất cả các ô trong hình vuông đó (từ 1 chuyển về 0, hoặc từ 0 chuyển về 1). Mỗi hình vuông 3*3 không được chọn quá một lần. 

Nhiệm vụ của bạn là tìm một dãy ít thao tác nhất sao cho sau khi thực hiện thì bảng chỉ còn chứa số 0. In ra tọa độ ô trái trên của các hình vuông 3*3 với tọa độ hàng tăng dần (nếu hai ô có cùng tọa độ hàng thì hình vuông nào có tọa độ cột của ô trái trên nhỏ hơn sẽ được in trước). Nếu không thể đưa bảng về toàn số 0 thì in ra -1. Nếu có nhiều phương án, bạn có thể in ra phương án bất kỳ.

Input

• Dòng 1: Chứa 2 số nguyên M và N (M, N ≤ 100).
• M dòng tiếp theo: mỗi dòng chứa N số 0 hoặc 1.

Output

• Dòng đầu chứa số K - số thao tác bạn thực hiện (nếu không tồn tại dãy thao tác thỏa mãn yêu cầu thì chỉ in ra duy nhất số -1).
• K dòng tiếp theo mô tả K thao tác được thực hiện, mỗi dòng chứa  2 số nguyên dương là tọa độ ô trái trên của các hình vuông 3*3.

Giới hạn

• Tất cả các test có M, N ≤ 100.
• Trong 40% test (tương ứng với 40% số điểm), M*N ≤ 18.
• Trong quá trình thi, bài của bạn chỉ được chấm với test ví dụ. Nếu được chấm đúng, kết quả sẽ được hiện là 100.

Ví dụ

Input:

5 5
1 1 0 1 1
1 1 0 1 1
1 0 1 0 1
0 1 1 1 0
0 1 1 1 0

Output:

3
1 1
1 3
3 2

Giải thích

Ở test ví dụ này chỉ có 1 cách duy nhất thỏa mãn: Bạn cần đảo bit 3 hình vuông:

• Hình có góc trên trái ở (1, 1)
• Hình có góc trên trái ở (1, 3)
• Hình có góc trên trái ở (3, 2)