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

Tuy mới 10 tuổi, nhưng Bé đã rất thích chơi với các số nhị phân. Hàng ngày, Bé thường lấy 1 tấm bảng kích thước M*N và chơi một trò chơi như sau:

• Ban đầu, trên mỗi ô của bảng ghi một bit 0 hoặc 1.
• Mỗi nước đi, Bé chọn một vùng hình chữ nhật nằm hoàn toàn trong bảng, có các cạnh song song với các cạnh của bảng, và có kích thước R*C, và đảo bit tất cả các ô trong vùng đó.
• Mục tiêu của Bé là đưa tất cả các ô trên bảng về bit 0.
• Bé không thích sự lặp lại, vì thế Bé sẽ không bao giờ thực hiện 2 nước đi (R1, C1) và (R2, C2) mà R1 = R2 và C1 = C2 (Nói cách khác, Bé không bao giờ thực hiện 2 nước đi có cùng cả R và C).

Hôm nay Bé bị ốm, không thể chơi được. Bạn hãy giúp bé chơi trò chơi này nhé.

Các hàng của bảng được đánh số từ 1 đến M từ trên xuống dưới, các cột của bảng được đánh số từ 1 đến N từ trái sang phải. Ô ở hàng i, cột j của bảng được kí hiệu là ô (i, j).

Input

• Dòng 1: Gồm 2 số nguyên dương M và N, là kích thước của bảng.
• M dòng tiếp theo, mỗi dòng gồm đúng N kí tự 0 hoặc 1, thể hiện trạng thái ban đầu của bảng.

Output

• Dòng 1: Gồm số nguyên dương Q duy nhất là số nước đi mà bạn thực hiện.
• Q dòng tiếp theo, mỗi dòng gồm đúng 4 số nguyên dương x, y, R, C thể hiện vùng mà bạn chọn, trong đó (x, y) là tọa độ ô trái trên của vùng được chọn, R và C là kích thước của vùng được chọn.

Giới hạn

• Trong 40% số test, 1 ≤ M, N ≤ 5
• Trong 60% test còn lại, 1 ≤ M, N ≤ 1000

Chấm điểm

• Bạn chỉ được điểm nếu dãy các nước di chuyển của bạn đưa bảng về gồm toàn bit 0.

Ví dụ

Input:
3 4
1000
0110
0000

Output:
2
1 1 1 1
2 2 1 2

Output sau KHÔNG hợp lệ (vùng kích thước 1*1 bị dùng 3 lần):
3
1 1 1 1
2 2 1 1
2 3 1 1