Circuit Board Wiring Problem

Bajtel company manufactures circuit boards of size \(n \times m\). Initially, only the cell at \((1,1)\) is powered. We can add wiring between any two adjacent grid cells so that power flows from one to the other. A set of wirings (edges) forms a connected circuit. You must choose exactly \(n \times m - 1\) wires (i.e. build a spanning tree over the grid) so that:

• The power reaches every cell, and
• The length of the longest connected circuit (i.e. the diameter of the tree measured in number of wires) is exactly \(k\).

Two cells are considered adjacent if they share a side. It is known that a Hamiltonian path (a path covering all cells, with diameter \(n\times m-1\)) is always a valid wiring if \(k = n\times m - 1\). In this problem, if \(k \neq n\times m - 1\) then no solution is required and you should output -1.

Given \(n\), \(m\) and \(k\) as input, output any valid wiring scheme (in any order) that meets the requirements, or output -1 if \(k \neq n\times m - 1\).

inputFormat

The input consists of three integers \(n\), \(m\) and \(k\) separated by spaces or newlines. \(n\) and \(m\) denote the board dimensions, and \(k\) is the required maximum length of the connected circuit (diameter of the spanning tree).

You may assume \(n,m \ge 1\) and \(0 \le k \le n\times m - 1\).

outputFormat

If a valid wiring scheme exists, print exactly \(n\times m - 1\) lines. Each line should contain four integers \(r_1\), \(c_1\), \(r_2\) and \(c_2\), indicating that an electric connection is drawn between cell \((r_1, c_1)\) and cell \((r_2, c_2)\). The two cells must be adjacent. If \(k \neq n\times m - 1\) (i.e. if no solution is implemented), output a single line with -1.

sample

2 2 3

1 1 1 2
1 2 2 2
2 2 2 1