A mosaic is laid out as an R-by-C grid of integer tile shades. An artist wants each main diagonal band to run smoothly from dark to light. A main diagonal band is the set of cells that share the same value of (row index minus column index); each band runs from its top-left cell toward the bottom-right.
Within each band, sort the values in ascending order, placing the smallest value at the top-left end of the band and the largest at the bottom-right end. Cells in different bands do not mix.
Print the resulting grid.
Input format
Line 1: two integers R and C.
Next R lines: each contains C space-separated integers (one grid row).
Output format
R lines, each with C space-separated integers: the grid after every diagonal band is sorted ascending.
Constraints
- 1 <= R, C <= 200
- -1000000000 <= each value <= 1000000000