Largest Rectangle with Area Limit

You are given an n x m grid. Your task is to find the coordinates of the largest rectangular region (by area), such that its area does not exceed a given limit L. The rectangle's area is computed by the formula \(A = h \times w\), where \(h\) is the height (number of rows) and \(w\) is the width (number of columns). The rectangle must reside entirely within the grid and its top-left corner is fixed at the coordinate (1, 1). Output the coordinates as four integers: the row and column of the top-left corner, followed by the row and column of the bottom-right corner.

Note: If multiple solutions yield the same maximum area, any valid one will be accepted.

inputFormat

The input is read from stdin and consists of three space-separated integers:

• n (1 ≤ n ≤ 10⁵): the number of rows in the grid.
• m (1 ≤ m ≤ 10⁵): the number of columns in the grid.
• L (1 ≤ L ≤ n*m): the maximum allowed area of the rectangle.

outputFormat

Output four space-separated integers to stdout representing the coordinates: r1 c1 r2 c2, where (r1, c1) is the top-left corner (always (1,1) in this problem) and (r2, c2) is the bottom-right corner of the rectangle with the largest possible area not exceeding L.

5 3 6

1 1 2 3