Heat Map

Heat Map

English translation by SOTA – AI Community of the Russian original. Organisers who would like this translation removed can email [email protected].

Task 6 of the municipal stage (Moscow) of the All-Russian School Olympiad (VsOSh) 2025/26 in artificial intelligence, grades 9–11 (variant III). Original: tasks-ai-9-11-mun-msk-25-26.pdf.

Time limit: 1 second
Memory limit: 256 megabytes

Slava is preparing a poster for a conference. Unfortunately, his heat map does not fit on the poster at the moment: it is too large. So Slava decided to select some rectangular fragment of the current map and use it for the presentation. Slava's heat map looks like a table of $n$ rows and $m$ columns. The cell at the intersection of the $i$-th row and the $j$-th column has colour $c_{ij}$. There are $k$ colours in use, numbered from 1 to $k$. An example of a similar map is shown on the right. Slava wants to show the whole range of values, so the selected fragment must contain at least one cell of each colour. At the same time, the young speaker wants to minimise the area of the map, because he needs to fit it on the poster.

[Figure: an example heat map, printed to the right of this text; see page 4 of the original PDF.]

Help him: find a rectangle that can be cut out of his map so that it contains cells of all $k$ colours. It is guaranteed that the original heat map contains cells of all $k$ colours.

Input format

The first line contains three natural numbers $n, m, k$ ($1 \leqslant n, m \leqslant 250$, $1 \leqslant k \leqslant 20$).
Each of the next $n$ lines contains $m$ natural numbers $c_{ij}$ ($1 \leqslant c_{ij} \leqslant k$).

Output format

Output 4 numbers $x_1, y_1, x_2, y_2$ that define the rectangle to be cut out. The rectangle is given by its top and bottom rows ($x_1$, $x_2$) and its left and right columns ($y_1$, $y_2$). If there are several ways to cut out a chart of the smallest area, output any of them.

Examples

Standard input:

3 4 3
1 1 2 2
3 1 1 3
1 2 2 2

Standard output:

1 3 2 4

Note

[Figure: see page 4 of the original PDF. Transcription: the $3 \times 4$ map of the example, with three dashed outlines marking rows 2–3 × columns 1–2 (red), rows 1–2 × columns 3–4 (orange) and rows 2–3 × columns 3–4 (purple).]

All possible ways to cut out a chart of the smallest area for the first example.

Scoring criterion: exact match of the answer — 100 points

Maximum score for the task — 100