Problem: Koa the Koala has a matrix A of n rows and m columns. Elements of this matrix are distinct integers from 1 to n ⋅ m (each number from 1 to n ⋅ m appears exactly once in the matrix).

For any matrix M of n rows and m columns let's define the following:

  * The i-th row of M is defined as R_i(M) = [ M_{i1}, M_{i2}, …, M_{im} ] for all i (1 ≤ i ≤ n). 
  * The j-th column of M is defined as C_j(M) = [ M_{1j}, M_{2j}, …, M_{nj} ] for all j (1 ≤ j ≤ m). 



Koa defines S(A) = (X, Y) as the spectrum of A, where X is the set of the maximum values in rows of A and Y is the set of the maximum values in columns of A.

More formally:

  * X = \{ max(R_1(A)), max(R_2(A)), …, max(R_n(A)) \} 
  * Y = \{ max(C_1(A)), max(C_2(A)), …, max(C_m(A)) \}



Koa asks you to find some matrix A' of n rows and m columns, such that each number from 1 to n ⋅ m appears exactly once in the matrix, and the following conditions hold:

  * S(A') = S(A) 
  * R_i(A') is bitonic for all i (1 ≤ i ≤ n) 
  * C_j(A') is bitonic for all j (1 ≤ j ≤ m) 

An array t (t_1, t_2, …, t_k) is called bitonic if it first increases and then decreases.

More formally: t is bitonic if there exists some position p (1 ≤ p ≤ k) such that: t_1 < t_2 < … < t_p > t_{p+1} > … > t_k.

Help Koa to find such matrix or to determine that it doesn't exist.

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 250) — the number of rows and columns of A.

Each of the ollowing n lines contains m integers. The j-th integer in the i-th line denotes element A_{ij} (1 ≤ A_{ij} ≤ n ⋅ m) of matrix A. It is guaranteed that every number from 1 to n ⋅ m appears exactly once among elements of the matrix.

Output

If such matrix doesn't exist, print -1 on a single line.

Otherwise, the output must consist of n lines, each one consisting of m space separated integers — a description of A'.

The j-th number in the i-th line represents the element A'_{ij}.

Every integer from 1 to n ⋅ m should appear exactly once in A', every row and column in A' must be bitonic and S(A) = S(A') must hold.

If there are many answers print any.

Examples

Input


3 3
3 5 6
1 7 9
4 8 2


Output


9 5 1
7 8 2
3 6 4


Input


2 2
4 1
3 2


Output


4 1
3 2


Input


3 4
12 10 8 6
3 4 5 7
2 11 9 1


Output


12 8 6 1
10 11 9 2
3 4 5 7

Note

Let's analyze the first sample:

For matrix A we have:

    * Rows: 
      * R_1(A) = [3, 5, 6]; max(R_1(A)) = 6 
      * R_2(A) = [1, 7, 9]; max(R_2(A)) = 9 
      * R_3(A) = [4, 8, 2]; max(R_3(A)) = 8 

    * Columns: 
      * C_1(A) = [3, 1, 4]; max(C_1(A)) = 4 
      * C_2(A) = [5, 7, 8]; max(C_2(A)) = 8 
      * C_3(A) = [6, 9, 2]; max(C_3(A)) = 9 

  * X = \{ max(R_1(A)), max(R_2(A)), max(R_3(A)) \} = \{ 6, 9, 8 \} 
  * Y = \{ max(C_1(A)), max(C_2(A)), max(C_3(A)) \} = \{ 4, 8, 9 \} 
  * So S(A) = (X, Y) = (\{ 6, 9, 8 \}, \{ 4, 8, 9 \}) 



For matrix A' we have:

    * Rows: 
      * R_1(A') = [9, 5, 1]; max(R_1(A')) = 9 
      * R_2(A') = [7, 8, 2]; max(R_2(A')) = 8 
      * R_3(A') = [3, 6, 4]; max(R_3(A')) = 6 

    * Columns: 
      * C_1(A') = [9, 7, 3]; max(C_1(A')) = 9 
      * C_2(A') = [5, 8, 6]; max(C_2(A')) = 8 
      * C_3(A') = [1, 2, 4]; max(C_3(A')) = 4 

  * Note that each of this arrays are bitonic. 
  * X = \{ max(R_1(A')), max(R_2(A')), max(R_3(A')) \} = \{ 9, 8, 6 \} 
  * Y = \{ max(C_1(A')), max(C_2(A')), max(C_3(A')) \} = \{ 9, 8, 4 \} 
  * So S(A') = (X, Y) = (\{ 9, 8, 6 \}, \{ 9, 8, 4 \}) 

Solution (in JAVA):

Solution:
import java.io.*;
import java.lang.Math;
import java.util.*;

public class Main  {

    public BufferedReader in;
    public PrintStream out;

    public boolean log_enabled = false;
    
    public boolean multiply_tests = false;

    private class TestCase {

        public Object solve() {
            
            int n = readInt(), m = readInt();
            
            int i,j;
            
            int[][] A = new int[n][m];
            
            for (i=0; i<n; i++)
            {
                for (j=0; j<m; j++)
                {
                    A[i][j] = n*m-readInt();
                }
            }
            
            int[] R = new int[n];
            int[] C = new int[m];
            
            Arrays.fill(R, n*m);
            Arrays.fill(C, n*m);
            
            for (i=0; i<n; i++)
            {
                for (j=0; j<m; j++)
                {
                    if (A[i][j] < R[i])
                    {
                        R[i] = A[i][j];
                    }
                    if (A[i][j] < C[j])
                    {
                        C[j] = A[i][j];
                    }
                }
            }
            
            boolean[] inR = new boolean[n*m];
            boolean[] inC = new boolean[n*m];
            
            Arrays.fill(inR, false);
            Arrays.fill(inC, false);
            
            for (i=0; i<n; i++)
            {
                inR[ R[i] ] = true;
            }
            
            for (j=0; j<m; j++)
            {
                inC[ C[j] ] = true;
            }
            
            boolean[] Rh = new boolean[n];
            boolean[] Ch = new boolean[m];
            
            Arrays.fill(Rh, false);
            Arrays.fill(Ch, false);
            
            int[][] Rf = new int[n][2];
            int[][] Cf = new int[m][2];
            
            int k, r, c, _r, _c;
            
           /* A[1][1] = n*m;
            Rh[1] = true;
            Ch[1] = true;
            
            Rf[1][0] = 0;
            Rf[1][1] = 2;
                    
            Cf[1][0] = 0;
            Cf[1][1] = 2;*/
            
            for (k=0; k<n*m; k++)
            {
                r = -1;
                c = -1;
                    
                if (inR[k] && inC[k])
                {
                    for (i=0; i<n; i++)
                    {
                        if (!Rh[i])
                        {
                            r = i;
                            break;
                        }
                    }
                    
                    for (j=0; j<m; j++)
                    {
                        if (!Ch[j])
                        {
                            c = j;
                            break;
                        }
                    }
                    
                    if ((r==-1)||(c==-1))
                    {
                        return -1;
                    }
                    
                    Rh[r] = true;
                    Ch[c] = true;
                    
                    Rf[r][0] = c-1;
                    Rf[r][1] = c+1;
                    
                    Cf[c][0] = r-1;
                    Cf[c][1] = r+1;
                }
                else if (inR[k])
                {
                    for (j=0; j<m; j++)
                    {
                        if (Ch[j] && ( ( (Cf[j][0]>=0) &&  !Rh[Cf[j][0]]) || ((Cf[j][1] < n) && !Rh[Cf[j][1]]) ))
                        {
                            if ((Cf[j][0]>=0) && !Rh[Cf[j][0]])
                            {
                                r = Cf[j][0];
                                Cf[j][0]--;
                            }
                            else
                            {
                                r = Cf[j][1];
                                Cf[j][1]++;
                            }
                            
                            c = j;
                            Rh[r] = true;
                            
                            Rf[r][0] = c-1;
                            Rf[r][1] = c+1;
                            
                            break;
                        }
                    }
                }
                else if (inC[k])
                {
                    for (i=0; i<n; i++)
                    {
                        if (Rh[i] && ( ( (Rf[i][0]>=0) && !Ch[Rf[i][0]]) || ((Rf[i][1] < m) && !Ch[Rf[i][1]]) ))
                        {
                            if ((Rf[i][0]>=0) && !Ch[Rf[i][0]])
                            {
                                c = Rf[i][0];
                                Rf[i][0]--;
                            }
                            else
                            {
                                c = Rf[i][1];
                                Rf[i][1]++;
                            }
                            
                            r = i;
                            Ch[c] = true;
                            
                            Cf[c][0] = r-1;
                            Cf[c][1] = r+1;
                            
                            break;
                        }
                    }
                }
                else
                {
                    for (i=0; i<n;i++)
                    {
                        if (!Rh[i]) continue;
                        
                        if (Rf[i][0]>=0)
                        {
                            j = Rf[i][0];
                            if (Ch[j] && ( Cf[j][0]==i || Cf[j][1]==i  ) )
                            {
                                r = i;
                                c = j;
                                
                                if (Cf[j][0]==i)
                                {
                                    Cf[j][0] --;
                                }
                                else
                                {
                                    Cf[j][1] ++;
                                }
                                
                                Rf[i][0] --;
                                
                                break;
                            }
                        }
                        
                        if (Rf[i][1]<m)
                        {
                            j = Rf[i][1];
                            if (Ch[j] && ( Cf[j][0]==i || Cf[j][1]==i  ) )
                            {
                                r = i;
                                c = j;
                                
                                if (Cf[j][0]==i)
                                {
                                    Cf[j][0] --;
                                }
                                else
                                {
                                    Cf[j][1] ++;
                                }
                                
                                Rf[i][1] ++;
                                
                                break;
                            }
                        }
                    }
                }
                
                if ((r>=0)&&(c>=0))
                {
                    A[r][c] = n*m-k;
                }
                else
                {
                    return -1;
                }                
                
            }
             
            
           /* for (i=0; i<n; i++)
            {
                c = A[i][0];
                A[i][0] = A[i][1];
                A[i][1] = c;
            }
            
            for (j=0; j<m; j++)
            {
                c = A[0][j];
                A[0][j] = A[1][j];
                A[1][j] = c;
            }*/
            
            for (i=0; i<n; i++)
            {
                for (j=0; j<m; j++)
                {
                    if (j>0) out.print(" ");
                    out.print(A[i][j]);
                }
                out.println();
            }
            
            return null;
            
            //return strf("%f", 0);
            
            //out.printf("Case #%d: \n", caseNumber);
            //return null;
        }
        
        public int caseNumber;
        
        TestCase(int number) {
            caseNumber = number;
        }
        
        public void run(){
            Object r = this.solve();
            
            if ((r != null))
            {
                //outputCaseNumber(r);
                out.println(r);
            }
        }
        
        public String impossible(){
            return "IMPOSSIBLE";
        }
        
        public String strf(String format, Object... args)
        {
            return String.format(format, args);
        }
        
//        public void outputCaseNumber(Object r){
//            //out.printf("Case #%d:", caseNumber);
//            if (r != null)
//            {
//              //  out.print(" ");
//                out.print(r);
//            }
//            out.print("\n");
//        }
    }

    public void run() {
        //while (true)
        {
            int t = multiply_tests ?  readInt() : 1;
            for (int i = 0; i < t; i++) {
                TestCase T = new TestCase(i + 1);
                T.run();
            }
        }
    }
    

    
    public Main(BufferedReader _in, PrintStream _out){
        in = _in;
        out = _out;
    }
    

    public static void main(String args[]) {
        Locale.setDefault(Locale.US);
        Main S;
        try {
            S = new Main(
                        new BufferedReader(new InputStreamReader(System.in)),
                        System.out
                );
        } catch (Exception e) {
            return;
        }
        
        S.run();
        
    }

    private StringTokenizer tokenizer = null;

    public int readInt() {
        return Integer.parseInt(readToken());
    }

    public long readLong() {
        return Long.parseLong(readToken());
    }

    public double readDouble() {
        return Double.parseDouble(readToken());
    }

    public String readLn() {
        try {
            String s;
            while ((s = in.readLine()).length() == 0);
            return s;
        } catch (Exception e) {
            return "";
        }
    }

    public String readToken() {
        try {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(in.readLine());
            }
            return tokenizer.nextToken();
        } catch (Exception e) {
            return "";
        }
    }

    public int[] readIntArray(int n) {
        int[] x = new int[n];
        readIntArray(x, n);
        return x;
    }

    public void readIntArray(int[] x, int n) {
        for (int i = 0; i < n; i++) {
            x[i] = readInt();
        }
    }
    
    public long[] readLongArray(int n) {
        long[] x = new long[n];
        readLongArray(x, n);
        return x;
    }

    public void readLongArray(long[] x, int n) {
        for (int i = 0; i < n; i++) {
            x[i] = readLong();
        }
    }

    public void logWrite(String format, Object... args) {
        if (!log_enabled) {
            return;
        }

        out.printf(format, args);
    }
}