Minimum Cubes for Achieving Opaque Views

A transparent rectangular prism (or cuboid) has dimensions \(n, m, k\) with \(n \ge m \ge k\). It is divided into \(n\times m\times k\) unit cubes. Each unit cube is identified by its coordinates \((a,b,c)\) where \(1 \le a \le n\), \(1 \le b \le m\), and \(1 \le c \le k\).

You may choose some of these \(1\times1\times1\) cubes and paint them black. The cuboid becomes opaque if and only if, when it is observed from the front, the side, and the top, there is no transparent (unpainted) area; in other words, each projection is completely covered by at least one painted cube along the corresponding line of sight.

The three views can be interpreted as follows:

• Top view: The projection on the \((a,b)\) plane. Every pair \((a,b)\) for \(1 \le a \le n\) and \(1 \le b \le m\) must appear at least once among the painted cubes.
• Front view: The projection on the \((a,c)\) plane. Every pair \((a,c)\) for \(1 \le a \le n\) and \(1 \le c \le k\) must appear at least once.
• Side view: The projection on the \((b,c)\) plane. Every pair \((b,c)\) for \(1 \le b \le m\) and \(1 \le c \le k\) must appear at least once.

Your task is to choose the smallest number of cubes to paint such that all three views are fully opaque, and output one valid scheme. If there are multiple optimal solutions, output any one of them.

Observation and Construction:

You must cover every top cell \((a,b)\). Hence, at a minimum you must paint \(n\times m\) cubes. It turns out that one optimal strategy is to paint exactly \(n\times m\) cubes by assigning each top cell \((a,b)\) a unique cube with a specific \(c\)-coordinate chosen as follows:

[ c = ((a+b-2) \bmod k) + 1. ]

This assignment guarantees that for every fixed \(a\) (or \(b\)), as \(b\) (or \(a\)) varies, the set of chosen \(c\)-values covers \(\{1,2,\dots,k\}\) because \(m \ge k\) and \(n \ge k\). Therefore, all three required projections are fully covered.

inputFormat

The input consists of a single line containing three integers \(n\), \(m\), and \(k\) (with \(n \ge m \ge k\)).

outputFormat

On the first line, output an integer representing the minimum number of cubes to paint, which will always be \(n \times m\). Each of the next \(n \times m\) lines should contain three integers \(a\), \(b\), \(c\) representing the coordinates of a painted cube. The scheme must satisfy the condition that the projections from the top, front, and side are completely covered.

sample

1 1 1

1
1 1 1