Drop Numbers to the Bottom

You are given a grid with N rows and M columns. Each entry of the grid is an integer. A cell with value -1 represents an empty cell. Your task is to simulate a gravity effect on the grid so that all numbers fall to the bottom of their respective columns while the empty cells (i.e. cells with -1) rise to the top.

For each column, the relative order of the non-empty numbers must be preserved as they drop. Formally, for every column, after the gravity effect, if the non-empty elements read from bottom to top are a₁, a₂, ... , a_k then these must be in the same order as in the original column.

Note: The empty cell is denoted by \( -1 \).

inputFormat

The first line contains two space-separated integers \( N \) and \( M \), indicating the number of rows and columns respectively.

This is followed by \( N \) lines, each containing \( M \) space-separated integers representing the grid.

outputFormat

Output the modified grid in \( N \) lines. Each line should contain \( M \) space-separated integers representing the grid after all numbers have dropped to the bottom.

## sample

3 4
-1 2 3 -1
5 -1 -1 6
-1 7 -1 8

-1 -1 -1 -1
-1 2 -1 6
5 7 3 8

</p>