Making Onion Chips

An onion chip is a rectangular frame-shaped snack with an empty middle. One chip consists of the perimeter cells of an axis-aligned rectangle whose height and width are both at least 3. The cells strictly inside the rectangle are not part of the chip.

An N × N snack sheet is given. Each cell contains an integer: a positive number means that the cell has more seasoning than the standard amount, and a negative number means that it has less. The taste of a chip is the sum of the integers on its perimeter cells.

The cutting process is repeated M times. At each step, among all chips that can be made using only cells that have not already been cut away, choose one with the maximum taste, then cut away its perimeter cells. Perimeters of different chips must not overlap. The inside of a later chip may contain cells that were cut away earlier, because inside cells are not part of that chip.

Print the taste and position of each chip in the order it is cut. If it is impossible to complete all M cuts, print 0.

The first line contains two integers N and M: the size of the snack sheet and the number of chips to cut.

Each of the next N lines contains N integers describing the sheet.

Print M lines, one for each chip in cutting order.

For each chip, print five integers: its taste, the row and column of its upper-left corner, and the row and column of its lower-right corner.

Coordinates are 1-based. If it is impossible to cut M chips as required, print a single line containing 0.

If there is more than one valid answer, any one may be printed.

• 3 ≤ N ≤ 30
• 1 ≤ M ≤ 30
• Each seasoning value is an integer between -100 and 100, inclusive.