Reconstructing Overlapping Archaeological Buildings

Archaeologists have recently uncovered remnants of Greek and Roman architecture. The site can be modeled as an \(r \times c\) grid of square cells. For each cell, it is known whether a building trace exists (1 indicates the presence of construction, and 0 indicates its absence).

After extensive analysis, the experts concluded that the site contains two buildings from different periods. The floor plan of each building is a square (i.e. its footprint is a contiguous \(L \times L\) block of cells). Note that since the buildings are from different eras, their floor plans may spatially overlap. In other words, a cell can be covered by one or both square footprints.

Your task is to determine a possible location and side length for each building such that the union of the two squares exactly matches the given grid. The grid cell \((i,j)\) is marked as 1 if and only if it is covered by at least one of the two squares.

inputFormat

The first line contains two integers \(r\) and \(c\) (\(1 \le r, c \le 20\)) representing the number of rows and columns of the grid. Each of the following \(r\) lines contains a string of \(c\) characters. Each character is either 0 or 1, indicating respectively that there is no building trace or that a building trace was discovered in that cell.

outputFormat

If there exists a valid configuration, output six integers: \(i_1\), \(j_1\), \(L_1\), \(i_2\), \(j_2\), and \(L_2\). Here \((i_1, j_1)\) denotes the top-left cell (1-indexed) and \(L_1\) the side length of the first square, and similarly for the second square. The union of the two squares must exactly cover all cells marked 1 and no cell marked 0 can be covered by any square. If no such configuration exists output a single line with -1.

sample

3 3
100
000
001

1 1 1 3 3 1