Minimize Express Streets

You are given a grid representing an urban map with n rows and m columns of intersections. Your goal is to add express streets between intersections so that the express distance between any two intersections is minimized by connecting them with a limited number of express streets.

An express street is represented as a connection between two intersections with coordinates \((x_1, y_1)\) and \((x_2, y_2)\). The function should generate as many express streets as possible following a simplified zigzag strategy, but the total number of streets cannot exceed a given threshold k. Specifically, the algorithm iterates over intersection indices and, if possible, adds up to three candidate express streets per iteration. Finally, the function returns the first \(t = \min(\text{total available streets}, k)\) express streets.

Input: Three integers \(n\), \(m\), and \(k\) representing the grid dimensions and the maximum allowed number of express streets.

Output: The first line contains \(t\) (the number of express streets used). Each of the following \(t\) lines contains 4 space‐separated integers \(x_1\), \(y_1\), \(x_2\), \(y_2\) that describe one express street.

inputFormat

The input consists of a single line containing three space-separated integers: n (number of rows), m (number of columns), and k (the maximum number of express streets).

Read input from stdin.

outputFormat

Output the number of express streets used on the first line. Then output exactly that many lines, each with 4 integers representing the express street endpoints, separated by spaces. Write output to stdout.

## sample

5 4 3

3
1 1 3 3
1 4 3 4
5 1 4 3

</p>