Problem: The Dogeforces company has k employees. Each employee, except for lower-level employees, has at least 2 subordinates. Lower-level employees have no subordinates. Each employee, except for the head of the company, has exactly one direct supervisor. The head of the company is a direct or indirect supervisor of all employees. It is known that in Dogeforces, each supervisor receives a salary strictly more than all his subordinates.

The full structure of the company is a secret, but you know the number of lower-level employees and for each pair of lower-level employees, the salary of their common supervisor is known (if there are several such supervisors, then the supervisor with the minimum salary). You have to restore the structure of the company.

Input

The first line contains a single integer n (2 ≤ n ≤ 500) — the number of lower-level employees.

This is followed by n lines, where i-th line contains n integers a_{i,1}, a_{i,2}, ..., a_{i,n} (1 ≤ a_{i,j} ≤ 5000) — salary of the common supervisor of employees with numbers i and j. It is guaranteed that a_{i,j} = a_{j,i}. Note that a_{i,i} is equal to the salary of the i-th employee.

Output

In the first line, print a single integer k — the number of employees in the company.

In the second line, print k integers c_1, c_2, ..., c_k, where c_i is the salary of the employee with the number i.

In the third line, print a single integer r — the number of the employee who is the head of the company.

In the following k-1 lines, print two integers v and u (1 ≤ v, u ≤ k) — the number of the employee and his direct supervisor.

Note that the lower-level employees have numbers from 1 to n, and for the rest of the employees, you have to assign numbers from n+1 to k. If there are several correct company structures, you can print any of them.

Example

Input


3
2 5 7
5 1 7
7 7 4


Output


5
2 1 4 7 5 
4
1 5
2 5
5 4
3 4

Note

One of the possible structures in the first example: <image>

Solution (in JAVA):

Solution:
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.net.Inet4Address;
import java.io.*;
import static java.lang.Math.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Dogeforces
// public class ATWNT
{
    static InputReader in = new InputReader(System.in);
    static OutputWriter out = new OutputWriter(System.out);

    static int gid=1;
    static class Node {
        HashSet<Integer> childs;
        int salary = 0;
        int id = 0;

        Node() {
            childs = new HashSet<Integer>();
            id = gid++;
        }
    }
    static Node nodes[] = new Node[10003];

    static int getParent(int []pars, int e){
        if(pars[e] == e)return e;
        return pars[e] = getParent(pars, pars[e]);
    }

    public static void main(String[] args) throws java.lang.Exception {

        int n = in.nextInt();

        int parents[] = new int[10003];
        // boolean ischild[] = new boolean[10003];

        // for (int i = 1; i <= n; i++)
        //     nodes[i] = new Node(i);

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2] != 0? a[2] - b[2]: a[0]-b[0]);// {from, to, salary}

        Node salary[] = new Node[5001];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                in.nextInt();
            }
            nodes[i] = new Node();
            nodes[i].salary = in.nextInt();
            salary[nodes[i].salary] = nodes[i];
            parents[i] = i;
            for (int j = i+1; j <= n; j++) {
                pq.add(new int[] { i, j, in.nextInt() });
            }
        }


        while(!pq.isEmpty()){
            int e[] = pq.poll();

            int sal = e[2];

            int pa = getParent(parents, e[0]);
            int pb = getParent(parents, e[1]);
            

            if(nodes[pa].salary == sal){
                parents[pb] = pa;
                if(nodes[pa].id != pb)nodes[pa].childs.add(pb);
            }else if(nodes[pb].salary == sal){
                parents[pa] = pb;
                if(nodes[pb].id != pa)nodes[pb].childs.add(pa);
            }else{
                Node nthis = new Node();
                nthis.salary = sal;
                nodes[nthis.id] = nthis;
                
                parents[pa] = nthis.id;
                parents[pb] = nthis.id;
                nthis.childs.add(pa);
                nthis.childs.add(pb);
                
                parents[nthis.id] = nthis.id;
            }

            // if(parents[e[0]].id != salary[sal].id){
            //     // ischild[parents[e[0]].id] = true;
            //     salary[sal].childs.add(parents[e[0]]);
            // }
            // if(parents[e[1]].id != salary[sal].id){
            //     salary[sal].childs.add(parents[e[1]]);
            //     // ischild[parents[e[0]].id] = true;
            // }
            
            // parents[e[0]] = salary[sal];
            // parents[e[1]] = salary[sal];
            

            // for (int i = 0; i < 2; i++) {
            //     Node child = nodes[e[i]];

            //     while(parents[child.id] != null && parents[child.id].salary<sal){
            //         child = parents[child.id];
            //     }
                
            // }
        }

        out.printLine(gid-1);

        for(int i=1;i<gid;i++){
            out.print(nodes[i].salary+" ");
        }
        out.printLine();
        // int heads = 0;
        // for(int i=n+1;i<gid;i++){
        //     if(ischild[i]==false){
        //         out.printLine(i);
        //         break;
        //     }
        // }

        out.printLine(gid-1);

        for(int i=gid-1;i>=1;i--){
            Node nod = nodes[i];
            for(int e:nod.childs){
                out.printLine(e+" "+nod.id);
            }
        }

        // in.close();
        out.flush();
        out.close();
    }

    private static class InputReader implements AutoCloseable {

        /**
         * The default size of the InputReader's buffer is 2<sup>16</sup>.
         */
        private static final int DEFAULT_BUFFER_SIZE = 1 << 16;

        /**
         * The default stream for the InputReader is standard input.
         */
        private static final InputStream DEFAULT_STREAM = System.in;

        /**
         * The maximum number of accurate decimal digits the method
         * {@link #nextDoubleFast() nextDoubleFast()} can read. Currently this value is
         * set to 21 because it is the maximum number of digits a double precision float
         * can have at the moment.
         */
        private static final int MAX_DECIMAL_PRECISION = 21;

        // 'c' is used to refer to the current character in the stream
        private int c;

        // Variables associated with the byte buffer.
        private final byte[] buf;
        private final int bufferSize;
        private int bufIndex;
        private int numBytesRead;

        private final InputStream stream;

        // End Of File (EOF) character
        private static final byte EOF = -1;

        // New line character: '\n'
        private static final byte NEW_LINE = 10;

        // Space character: ' '
        private static final byte SPACE = 32;

        // Dash character: '-'
        private static final byte DASH = 45;

        // Dot character: '.'
        private static final byte DOT = 46;

        // A reusable character buffer when reading string data.
        private char[] charBuffer;

        // Primitive data type lookup tables used for optimizations
        private static final byte[] bytes = new byte[58];
        private static final int[] ints = new int[58];
        private static final char[] chars = new char[128];

        static {
            char ch = ' ';
            int value = 0;
            byte _byte = 0;
            for (int i = 48; i < 58; i++)
                bytes[i] = _byte++;
            for (int i = 48; i < 58; i++)
                ints[i] = value++;
            for (int i = 32; i < 128; i++)
                chars[i] = ch++;
        }

        // Primitive double lookup table used for optimizations.
        private static final double[][] doubles = {
                { 0.0d, 0.00d, 0.000d, 0.0000d, 0.00000d, 0.000000d, 0.0000000d, 0.00000000d, 0.000000000d,
                        0.0000000000d, 0.00000000000d, 0.000000000000d, 0.0000000000000d, 0.00000000000000d,
                        0.000000000000000d, 0.0000000000000000d, 0.00000000000000000d, 0.000000000000000000d,
                        0.0000000000000000000d, 0.00000000000000000000d, 0.000000000000000000000d },
                { 0.1d, 0.01d, 0.001d, 0.0001d, 0.00001d, 0.000001d, 0.0000001d, 0.00000001d, 0.000000001d,
                        0.0000000001d, 0.00000000001d, 0.000000000001d, 0.0000000000001d, 0.00000000000001d,
                        0.000000000000001d, 0.0000000000000001d, 0.00000000000000001d, 0.000000000000000001d,
                        0.0000000000000000001d, 0.00000000000000000001d, 0.000000000000000000001d },
                { 0.2d, 0.02d, 0.002d, 0.0002d, 0.00002d, 0.000002d, 0.0000002d, 0.00000002d, 0.000000002d,
                        0.0000000002d, 0.00000000002d, 0.000000000002d, 0.0000000000002d, 0.00000000000002d,
                        0.000000000000002d, 0.0000000000000002d, 0.00000000000000002d, 0.000000000000000002d,
                        0.0000000000000000002d, 0.00000000000000000002d, 0.000000000000000000002d },
                { 0.3d, 0.03d, 0.003d, 0.0003d, 0.00003d, 0.000003d, 0.0000003d, 0.00000003d, 0.000000003d,
                        0.0000000003d, 0.00000000003d, 0.000000000003d, 0.0000000000003d, 0.00000000000003d,
                        0.000000000000003d, 0.0000000000000003d, 0.00000000000000003d, 0.000000000000000003d,
                        0.0000000000000000003d, 0.00000000000000000003d, 0.000000000000000000003d },
                { 0.4d, 0.04d, 0.004d, 0.0004d, 0.00004d, 0.000004d, 0.0000004d, 0.00000004d, 0.000000004d,
                        0.0000000004d, 0.00000000004d, 0.000000000004d, 0.0000000000004d, 0.00000000000004d,
                        0.000000000000004d, 0.0000000000000004d, 0.00000000000000004d, 0.000000000000000004d,
                        0.0000000000000000004d, 0.00000000000000000004d, 0.000000000000000000004d },
                { 0.5d, 0.05d, 0.005d, 0.0005d, 0.00005d, 0.000005d, 0.0000005d, 0.00000005d, 0.000000005d,
                        0.0000000005d, 0.00000000005d, 0.000000000005d, 0.0000000000005d, 0.00000000000005d,
                        0.000000000000005d, 0.0000000000000005d, 0.00000000000000005d, 0.000000000000000005d,
                        0.0000000000000000005d, 0.00000000000000000005d, 0.000000000000000000005d },
                { 0.6d, 0.06d, 0.006d, 0.0006d, 0.00006d, 0.000006d, 0.0000006d, 0.00000006d, 0.000000006d,
                        0.0000000006d, 0.00000000006d, 0.000000000006d, 0.0000000000006d, 0.00000000000006d,
                        0.000000000000006d, 0.0000000000000006d, 0.00000000000000006d, 0.000000000000000006d,
                        0.0000000000000000006d, 0.00000000000000000006d, 0.000000000000000000006d },
                { 0.7d, 0.07d, 0.007d, 0.0007d, 0.00007d, 0.000007d, 0.0000007d, 0.00000007d, 0.000000007d,
                        0.0000000007d, 0.00000000007d, 0.000000000007d, 0.0000000000007d, 0.00000000000007d,
                        0.000000000000007d, 0.0000000000000007d, 0.00000000000000007d, 0.000000000000000007d,
                        0.0000000000000000007d, 0.00000000000000000007d, 0.000000000000000000007d },
                { 0.8d, 0.08d, 0.008d, 0.0008d, 0.00008d, 0.000008d, 0.0000008d, 0.00000008d, 0.000000008d,
                        0.0000000008d, 0.00000000008d, 0.000000000008d, 0.0000000000008d, 0.00000000000008d,
                        0.000000000000008d, 0.0000000000000008d, 0.00000000000000008d, 0.000000000000000008d,
                        0.0000000000000000008d, 0.00000000000000000008d, 0.000000000000000000008d },
                { 0.9d, 0.09d, 0.009d, 0.0009d, 0.00009d, 0.000009d, 0.0000009d, 0.00000009d, 0.000000009d,
                        0.0000000009d, 0.00000000009d, 0.000000000009d, 0.0000000000009d, 0.00000000000009d,
                        0.000000000000009d, 0.0000000000000009d, 0.00000000000000009d, 0.000000000000000009d,
                        0.0000000000000000009d, 0.00000000000000000009d, 0.000000000000000000009d } };

        /**
         * Create an InputReader that reads from standard input.
         */
        public InputReader() {
            this(DEFAULT_STREAM, DEFAULT_BUFFER_SIZE);
        }

        /**
         * Create an InputReader that reads from standard input.
         *
         * @param bufferSize The buffer size for this input reader.
         */
        public InputReader(int bufferSize) {
            this(DEFAULT_STREAM, bufferSize);
        }

        /**
         * Create an InputReader that reads from standard input.
         *
         * @param stream Takes an InputStream as a parameter to read from.
         */
        public InputReader(InputStream stream) {
            this(stream, DEFAULT_BUFFER_SIZE);
        }

        /**
         * Create an InputReader that reads from standard input.
         *
         * @param stream     Takes an {@link java.io.InputStream#InputStream()
         *                   InputStream} as a parameter to read from.
         * @param bufferSize The size of the buffer to use.
         */
        public InputReader(InputStream stream, int bufferSize) {
            if (stream == null || bufferSize <= 0)
                throw new IllegalArgumentException();
            buf = new byte[bufferSize];
            charBuffer = new char[128];
            this.bufferSize = bufferSize;
            this.stream = stream;
        }

        /**
         * Reads a single character from the input stream.
         *
         * @return Returns the byte value of the next character in the buffer and EOF at
         *         the end of the stream.
         * @throws IOException throws exception if there is no more data to read
         */
        private byte read() throws IOException {

            if (numBytesRead == EOF)
                throw new IOException();

            if (bufIndex >= numBytesRead) {
                bufIndex = 0;
                numBytesRead = stream.read(buf);
                if (numBytesRead == EOF)
                    return EOF;
            }

            return buf[bufIndex++];
        }

        /**
         * Read values from the input stream until you reach a character with a higher
         * ASCII value than 'token'.
         *
         * @param token The token is a value which we use to stop reading junk out of
         *              the stream.
         * @return Returns 0 if a value greater than the token was reached or -1 if the
         *         end of the stream was reached.
         * @throws IOException Throws exception at end of stream.
         */
        private int readJunk(int token) throws IOException {

            if (numBytesRead == EOF)
                return EOF;

            // Seek to the first valid position index
            do {

                while (bufIndex < numBytesRead) {
                    if (buf[bufIndex] > token)
                        return 0;
                    bufIndex++;
                }

                // reload buffer
                numBytesRead = stream.read(buf);
                if (numBytesRead == EOF)
                    return EOF;
                bufIndex = 0;

            } while (true);

        }

        /**
         * Reads a single byte from the input stream.
         *
         * @return The next byte in the input stream
         * @throws IOException Throws exception at end of stream.
         */
        public byte nextByte() throws IOException {
            return (byte) nextInt();
        }

        /**
         * Reads a 32 bit signed integer from input stream.
         *
         * @return The next integer value in the stream.
         * @throws IOException Throws exception at end of stream.
         */
        public int nextInt() throws IOException {

            if (readJunk(DASH - 1) == EOF)
                throw new IOException();
            int sgn = 1, res = 0;

            c = buf[bufIndex];
            if (c == DASH) {
                sgn = -1;
                bufIndex++;
            }

            do {

                while (bufIndex < numBytesRead) {
                    if (buf[bufIndex] > SPACE) {
                        res = (res << 3) + (res << 1);
                        res += ints[buf[bufIndex++]];
                    } else {
                        bufIndex++;
                        return res * sgn;
                    }
                }

                // Reload buffer
                numBytesRead = stream.read(buf);
                if (numBytesRead == EOF)
                    return res * sgn;
                bufIndex = 0;

            } while (true);

        }

        /**
         * Reads a 64 bit signed long from input stream.
         *
         * @return The next long value in the stream.
         * @throws IOException Throws exception at end of stream.
         */
        public long nextLong() throws IOException {

            if (readJunk(DASH - 1) == EOF)
                throw new IOException();
            int sgn = 1;
            long res = 0L;
            c = buf[bufIndex];
            if (c == DASH) {
                sgn = -1;
                bufIndex++;
            }

            do {

                while (bufIndex < numBytesRead) {
                    if (buf[bufIndex] > SPACE) {
                        res = (res << 3) + (res << 1);
                        res += ints[buf[bufIndex++]];
                    } else {
                        bufIndex++;
                        return res * sgn;
                    }
                }

                // Reload buffer
                numBytesRead = stream.read(buf);
                if (numBytesRead == EOF)
                    return res * sgn;
                bufIndex = 0;

            } while (true);

        }

        /**
         * Doubles the size of the internal char buffer for strings
         */
        private void doubleCharBufferSize() {
            char[] newBuffer = new char[charBuffer.length << 1];
            for (int i = 0; i < charBuffer.length; i++)
                newBuffer[i] = charBuffer[i];
            charBuffer = newBuffer;
        }

        /**
         * Reads a line from the input stream.
         *
         * @return Returns a line from the input stream in the form a String not
         *         including the new line character. Returns <code>null</code> when
         *         there are no more lines.
         * @throws IOException Throws IOException when something terrible happens.
         */
        public String nextLine() throws IOException {

            try {
                c = read();
            } catch (IOException e) {
                return null;
            }
            if (c == NEW_LINE)
                return ""; // Empty line
            if (c == EOF)
                return null; // EOF

            int i = 0;
            charBuffer[i++] = (char) c;

            do {

                while (bufIndex < numBytesRead) {
                    if (buf[bufIndex] != NEW_LINE) {
                        if (i == charBuffer.length)
                            doubleCharBufferSize();
                        charBuffer[i++] = (char) buf[bufIndex++];
                    } else {
                        bufIndex++;
                        return new String(charBuffer, 0, i);
                    }
                }

                // Reload buffer
                numBytesRead = stream.read(buf);
                if (numBytesRead == EOF)
                    return new String(charBuffer, 0, i);
                bufIndex = 0;

            } while (true);

        }

        // Reads a string of characters from the input stream.
        // The delimiter separating a string of characters is set to be:
        // any ASCII value <= 32 meaning any spaces, new lines, EOF, tabs...
        public String nextString() throws IOException {
            if (numBytesRead == EOF)
                return null;
            if (readJunk(SPACE) == EOF)
                return null;

            for (int i = 0;;) {
                while (bufIndex < numBytesRead) {
                    if (buf[bufIndex] > SPACE) {
                        if (i == charBuffer.length)
                            doubleCharBufferSize();
                        charBuffer[i++] = (char) buf[bufIndex++];
                    } else {
                        bufIndex++;
                        return new String(charBuffer, 0, i);
                    }
                }

                // Reload buffer
                numBytesRead = stream.read(buf);
                if (numBytesRead == EOF)
                    return new String(charBuffer, 0, i);
                bufIndex = 0;
            }
        }

        // Returns an exact value a double value from the input stream.
        public double nextDouble() throws IOException {
            String doubleVal = nextString();
            if (doubleVal == null)
                throw new IOException();
            return Double.valueOf(doubleVal);
        }

        // Very quickly reads a double value from the input stream (~3x faster than
        // nextDouble()). However,
        // this method may provide a slightly less accurate reading than .nextDouble()
        // if there are a lot
        // of digits (~16+). In particular, it will only read double values with at most
        // 21 digits after
        // the decimal point and the reading my be as inaccurate as ~5*10^-16 from the
        // true value.
        public double nextDoubleFast() throws IOException {
            c = read();
            int sgn = 1;
            while (c <= SPACE)
                c = read(); // while c is either: ' ', '\n', EOF
            if (c == DASH) {
                sgn = -1;
                c = read();
            }
            double res = 0.0;
            // while c is not: ' ', '\n', '.' or -1
            while (c > DOT) {
                res *= 10.0;
                res += ints[c];
                c = read();
            }
            if (c == DOT) {
                int i = 0;
                c = read();
                // while c is digit and we are less than the maximum decimal precision
                while (c > SPACE && i < MAX_DECIMAL_PRECISION) {
                    res += doubles[ints[c]][i++];
                    c = read();
                }
            }
            return res * sgn;
        }

        // Read an array of n byte values
        public byte[] nextByteArray(int n) throws IOException {
            byte[] ar = new byte[n];
            for (int i = 0; i < n; i++)
                ar[i] = nextByte();
            return ar;
        }

        // Read an integer array of size n
        public int[] nextIntArray(int n) throws IOException {
            int[] ar = new int[n];
            for (int i = 0; i < n; i++)
                ar[i] = nextInt();
            return ar;
        }

        // Read a long array of size n
        public long[] nextLongArray(int n) throws IOException {
            long[] ar = new long[n];
            for (int i = 0; i < n; i++)
                ar[i] = nextLong();
            return ar;
        }

        // read an of doubles of size n
        public double[] nextDoubleArray(int n) throws IOException {
            double[] ar = new double[n];
            for (int i = 0; i < n; i++)
                ar[i] = nextDouble();
            return ar;
        }

        // Quickly read an array of doubles
        public double[] nextDoubleArrayFast(int n) throws IOException {
            double[] ar = new double[n];
            for (int i = 0; i < n; i++)
                ar[i] = nextDoubleFast();
            return ar;
        }

        // Read a string array of size n
        public String[] nextStringArray(int n) throws IOException {
            String[] ar = new String[n];
            for (int i = 0; i < n; i++) {
                String str = nextString();
                if (str == null)
                    throw new IOException();
                ar[i] = str;
            }
            return ar;
        }

        // Read a 1-based byte array of size n+1
        public byte[] nextByteArray1(int n) throws IOException {
            byte[] ar = new byte[n + 1];
            for (int i = 1; i <= n; i++)
                ar[i] = nextByte();
            return ar;
        }

        // Read a 1-based integer array of size n+1
        public int[] nextIntArray1(int n) throws IOException {
            int[] ar = new int[n + 1];
            for (int i = 1; i <= n; i++)
                ar[i] = nextInt();
            return ar;
        }

        // Read a 1-based long array of size n+1
        public long[] nextLongArray1(int n) throws IOException {
            long[] ar = new long[n + 1];
            for (int i = 1; i <= n; i++)
                ar[i] = nextLong();
            return ar;
        }

        // Read a 1-based double array of size n+1
        public double[] nextDoubleArray1(int n) throws IOException {
            double[] ar = new double[n + 1];
            for (int i = 1; i <= n; i++)
                ar[i] = nextDouble();
            return ar;
        }

        // Quickly read a 1-based double array of size n+1
        public double[] nextDoubleArrayFast1(int n) throws IOException {
            double[] ar = new double[n + 1];
            for (int i = 1; i <= n; i++)
                ar[i] = nextDoubleFast();
            return ar;
        }

        // Read a 1-based string array of size n+1
        public String[] nextStringArray1(int n) throws IOException {
            String[] ar = new String[n + 1];
            for (int i = 1; i <= n; i++)
                ar[i] = nextString();
            return ar;
        }

        // Read a two dimensional matrix of bytes of size rows x cols
        public byte[][] nextByteMatrix(int rows, int cols) throws IOException {
            byte[][] matrix = new byte[rows][cols];
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    matrix[i][j] = nextByte();
            return matrix;
        }

        // Read a two dimensional matrix of ints of size rows x cols
        public int[][] nextIntMatrix(int rows, int cols) throws IOException {
            int[][] matrix = new int[rows][cols];
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    matrix[i][j] = nextInt();
            return matrix;
        }

        // Read a two dimensional matrix of longs of size rows x cols
        public long[][] nextLongMatrix(int rows, int cols) throws IOException {
            long[][] matrix = new long[rows][cols];
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    matrix[i][j] = nextLong();
            return matrix;
        }

        // Read a two dimensional matrix of doubles of size rows x cols
        public double[][] nextDoubleMatrix(int rows, int cols) throws IOException {
            double[][] matrix = new double[rows][cols];
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    matrix[i][j] = nextDouble();
            return matrix;
        }

        // Quickly read a two dimensional matrix of doubles of size rows x cols
        public double[][] nextDoubleMatrixFast(int rows, int cols) throws IOException {
            double[][] matrix = new double[rows][cols];
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    matrix[i][j] = nextDoubleFast();
            return matrix;
        }

        // Read a two dimensional matrix of Strings of size rows x cols
        public String[][] nextStringMatrix(int rows, int cols) throws IOException {
            String[][] matrix = new String[rows][cols];
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    matrix[i][j] = nextString();
            return matrix;
        }

        // Read a 1-based two dimensional matrix of bytes of size rows x cols
        public byte[][] nextByteMatrix1(int rows, int cols) throws IOException {
            byte[][] matrix = new byte[rows + 1][cols + 1];
            for (int i = 1; i <= rows; i++)
                for (int j = 1; j <= cols; j++)
                    matrix[i][j] = nextByte();
            return matrix;
        }

        // Read a 1-based two dimensional matrix of ints of size rows x cols
        public int[][] nextIntMatrix1(int rows, int cols) throws IOException {
            int[][] matrix = new int[rows + 1][cols + 1];
            for (int i = 1; i <= rows; i++)
                for (int j = 1; j <= cols; j++)
                    matrix[i][j] = nextInt();
            return matrix;
        }

        // Read a 1-based two dimensional matrix of longs of size rows x cols
        public long[][] nextLongMatrix1(int rows, int cols) throws IOException {
            long[][] matrix = new long[rows + 1][cols + 1];
            for (int i = 1; i <= rows; i++)
                for (int j = 1; j <= cols; j++)
                    matrix[i][j] = nextLong();
            return matrix;
        }

        // Read a 1-based two dimensional matrix of doubles of size rows x cols
        public double[][] nextDoubleMatrix1(int rows, int cols) throws IOException {
            double[][] matrix = new double[rows + 1][cols + 1];
            for (int i = 1; i <= rows; i++)
                for (int j = 1; j <= cols; j++)
                    matrix[i][j] = nextDouble();
            return matrix;
        }

        // Quickly read a 1-based two dimensional matrix of doubles of size rows x cols
        public double[][] nextDoubleMatrixFast1(int rows, int cols) throws IOException {
            double[][] matrix = new double[rows + 1][cols + 1];
            for (int i = 1; i <= rows; i++)
                for (int j = 1; j <= cols; j++)
                    matrix[i][j] = nextDoubleFast();
            return matrix;
        }

        // Read a 1-based two dimensional matrix of Strings of size rows x cols
        public String[][] nextStringMatrix1(int rows, int cols) throws IOException {
            String[][] matrix = new String[rows + 1][cols + 1];
            for (int i = 1; i <= rows; i++)
                for (int j = 1; j <= cols; j++)
                    matrix[i][j] = nextString();
            return matrix;
        }

        // Closes the input stream
        public void close() throws IOException {
            stream.close();
        }

    }

    private static class OutputWriter implements AutoCloseable {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0)
                    writer.print(' ');
                writer.print(objects[i]);
            }
        }

        public void printLine(Object... objects) {
            print(objects);
            writer.println();
        }

        public void close() {
            writer.close();
        }

        public void flush() {
            writer.flush();
        }

    }
}