Minimum Rectangle Covering of Black Cells

Given an \(N \times M\) matrix consisting of black and white cells, your task is to cover all black cells using as few rectangles as possible, subject to the following conditions:

• Each black cell is covered by exactly one rectangle.
• No two rectangles overlap.
• A rectangle cannot cover any white cell.

You need to output a valid covering scheme. In the output, first print the number of rectangles \(K\). Then, for each rectangle, output four integers \(r_1, c_1, r_2, c_2\) representing the top-left and bottom-right coordinates of the rectangle (using 1-indexed row and column numbers).

Note: Although an optimal solution minimizes the number of rectangles, any valid covering that follows the conditions is acceptable.

inputFormat

The first line contains two integers \(N\) and \(M\) (the number of rows and columns respectively). The following \(N\) lines each contain a string of length \(M\) consisting of characters '0' and '1', where '1' represents a black cell and '0' represents a white cell.

outputFormat

First, output an integer \(K\), representing the number of rectangles used. Then output \(K\) lines, each containing four integers \(r_1, c_1, r_2, c_2\) which denote the top-left and bottom-right coordinates (1-indexed) of each rectangle.

sample

3 3
111
111
111

1
1 1 3 3