Lexicographically Smallest Matrix

You are given a matrix \(G\) with \(R\) rows and \(C\) columns filled with positive integers. You are allowed to perform the following operation exactly once: choose any non-empty contiguous submatrix of \(G\) and sort its elements in non-descending order.

Your task is to determine the lexicographically smallest matrix that can be obtained after performing the operation.

Note: The lexicographical order of two matrices is determined by comparing their elements in row-major order.

For example, given the matrix:

\[ \begin{bmatrix} 10 & 20 & 30 \\ 5 & 15 & 35 \\ 1 & 25 & 40 \end{bmatrix} \]

After sorting all the elements and filling them back in row-major order, the lexicographically smallest matrix is:

\[ \begin{bmatrix} 1 & 5 & 10 \\ 15 & 20 & 25 \\ 30 & 35 & 40 \end{bmatrix} \]

inputFormat

The first line of input contains two integers (R) and (C), representing the number of rows and columns, respectively. This is followed by (R) lines, each containing (C) space-separated integers representing the matrix (G).

outputFormat

Output the lexicographically smallest matrix. Print (R) lines where each line contains (C) space-separated integers representing a row of the matrix.## sample

3 3
10 20 30
5 15 35
1 25 40

1 5 10
15 20 25
30 35 40

</p>