1383_D. Rearrange_28584
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 \}) 
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);
    }
}

3 3
3 5 6
1 7 9
4 8 2
 3 4
12 10 8 6
3 4 5 7
2 11 9 1
 2 2
4 1
3 2
 9 14
103 120 6 12 5 68 122 22 33 3 121 105 53 54
63 34 99 77 20 66 24 94 51 65 16 25 125 31
49 56 104 57 119 118 72 28 23 85 9 48 60 71
82 47 43 110 7 115 41 18 126 100 79 102 109 13
90 80 46 44 45 108 61 40 101 107 21 62 74 11
91 124 26 87 38 88 81 75 59 36 67 78 17 106
92 19 116 113 117 10 93 64 30 50 42 2 8 114
83 111 4 73 14 95 27 32 58 86 15 96 84 35
98 97 39 112 29 37 1 52 89 70 76 55 123 69
 10 10
66 79 1 37 45 57 30 94 40 93
52 62 83 82 12 88 32 59 34 47
75 8 64 41 78 60 29 86 96 68
42 89 58 76 24 100 92 3 14 35
23 39 49 43 10 28 19 48 15 51
55 36 85 26 5 4 16 11 33 7
98 27 18 87 65 72 38 70 69 2
53 22 44 71 97 6 80 61 13 74
31 95 56 63 54 91 21 99 73 84
81 46 25 67 17 9 50 90 20 77
 1 1
1
 11 12
18 11 13 33 2 122 131 91 95 103 117 100
108 49 27 128 24 86 74 83 56 89 61 75
124 120 62 78 67 35 125 39 111 37 68 69
57 42 98 80 52 123 32 121 106 16 90 31
30 65 96 38 73 36 81 63 53 77 28 6
9 79 23 26 1 87 92 88 54 84 109 55
12 114 113 64 21 59 4 66 118 110 5 48
19 115 119 15 47 51 29 44 82 76 102 8
97 10 7 112 99 132 94 72 126 130 129 60
46 20 17 70 50 93 58 101 34 43 22 14
104 41 71 105 116 40 127 85 107 3 25 45
 5 8
14 20 36 25 31 29 11 24
16 2 27 1 33 13 35 38
12 8 37 30 10 7 32 19
40 18 26 3 17 23 22 9
6 15 34 21 39 5 4 28
 1 4
4 1
3 2

9 5 1 
7 8 2 
3 6 4 
 12 8 6 1 
10 11 9 2 
3 4 5 7 
 4 1 
3 2 
 126 115 106 95 90 80 75 63 57 51 25 17 9 1 
120 125 109 96 91 81 76 64 58 52 26 18 10 2 
110 112 124 97 92 82 77 65 59 53 27 19 11 3 
102 104 123 98 93 83 78 66 60 54 28 20 12 4 
99 100 101 122 121 84 79 67 61 55 29 21 13 5 
85 86 87 88 89 119 118 68 62 56 30 22 14 6 
69 70 71 72 73 74 117 116 114 113 31 23 15 7 
42 43 44 45 46 47 48 49 50 111 32 24 16 8 
33 34 35 36 37 38 39 40 41 108 107 105 103 94 
 100 89 82 76 68 64 54 48 27 10 
91 99 83 77 69 65 55 49 28 11 
84 86 98 78 70 66 56 50 29 12 
79 80 81 97 71 67 57 52 30 13 
72 73 74 75 96 95 58 53 31 14 
59 60 61 62 63 94 93 92 32 15 
41 42 43 44 45 46 47 90 33 16 
34 35 36 37 38 39 40 88 87 17 
18 19 20 21 22 23 24 25 26 85 
1 2 3 4 5 6 7 8 9 51 
 1 
 132 117 115 114 107 98 88 77 72 57 41 12 
122 131 130 129 108 99 89 78 73 58 42 13 
110 111 112 113 128 102 90 79 74 59 43 14 
103 104 105 106 127 126 91 80 75 60 44 15 
92 93 94 95 97 125 124 81 76 61 45 16 
82 83 84 85 86 87 123 121 120 62 46 17 
63 64 65 66 67 68 69 70 71 119 47 18 
48 49 50 51 52 53 54 55 56 118 116 19 
31 32 33 34 35 36 37 38 39 40 109 20 
21 22 23 24 25 26 27 28 29 30 101 100 
1 2 3 4 5 6 7 8 9 10 11 96 
 40 33 27 21 13 9 5 1 
34 39 28 22 14 10 6 2 
31 32 38 23 15 11 7 3 
24 25 26 37 16 12 8 4 
17 18 19 36 35 30 29 20 
 4 3 2 1 
