Problem: A permutation — is a sequence of length n integers from 1 to n, in which all the numbers occur exactly once. For example, [1], [3, 5, 2, 1, 4], [1, 3, 2] — permutations, and [2, 3, 2], [4, 3, 1], [0] — no.

Polycarp was recently gifted a permutation a[1 ... n] of length n. Polycarp likes trees more than permutations, so he wants to transform permutation a into a rooted binary tree. He transforms an array of different integers into a tree as follows: 

  * the maximum element of the array becomes the root of the tree; 
  * all elements to the left of the maximum — form a left subtree (which is built according to the same rules but applied to the left part of the array), but if there are no elements to the left of the maximum, then the root has no left child; 
  * all elements to the right of the maximum — form a right subtree (which is built according to the same rules but applied to the right side of the array), but if there are no elements to the right of the maximum, then the root has no right child. 



For example, if he builds a tree by permutation a=[3, 5, 2, 1, 4], then the root will be the element a_2=5, and the left subtree will be the tree that will be built for the subarray a[1 ... 1] = [3], and the right one — for the subarray a[3 ... 5] = [2, 1, 4]. As a result, the following tree will be built: 

<image> The tree corresponding to the permutation a=[3, 5, 2, 1, 4].

Another example: let the permutation be a=[1, 3, 2, 7, 5, 6, 4]. In this case, the tree looks like this: 

<image> The tree corresponding to the permutation a=[1, 3, 2, 7, 5, 6, 4].

Let us denote by d_v the depth of the vertex a_v, that is, the number of edges on the path from the root to the vertex numbered a_v. Note that the root depth is zero. Given the permutation a, for each vertex, find the value of d_v.

Input

The first line contains one integer t (1 ≤ t ≤ 100) — the number of test cases. Then t test cases follow.

The first line of each test case contains an integer n (1 ≤ n ≤ 100) — the length of the permutation.

This is followed by n numbers a_1, a_2, …, a_n — permutation a.

Output

For each test case, output n values — d_1, d_2, …, d_n.

Example

Input


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


Output


1 0 2 3 1 
0 
0 1 3 2 

Solution (in JAVA):

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

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

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

    // Node head;
    // Node tail;
    // class Node{
    //     int d;
    //     Node prev;
    //     Node next;
    //     Node(int e){
    //         d= e;
    //     }
    //     static void add(int e){
    //         Node e = new
    //     }
    // }

    static int getMax(int i, int j, int ar[], int index[]){
        int max = i;

        while(i<=j){
            if(ar[i] > ar[max]){
                max = i;
            }
            i++;
        }
        return max;
    }
    
    public static void main(String[] args) throws java.lang.Exception {

        int t = in.nextInt();

        while(t-->0){
            int n = in.nextInt();
            int ar[] = in.nextIntArray(n);
            int index[] = new int[101];
            int ans[] = new int[n];

            for(int i=0;i<n;i++){
                index[ar[i]] = i;
            }

            cal(0, 0, n-1, ar, index, ans);

            for(int e:ans){
                out.print(e+" ");
            }
            out.printLine();
        }

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

    static void cal(int d, int i, int j, int[]ar, int[]index, int[]ans){
        if(j<i)return;
        if(i==j){
            ans[i] = d;
            return;
        }

        int maxInd = getMax(i, j, ar, index);

        ans[maxInd] = d;

        cal(d+1, i, maxInd-1, ar, index, ans);
        cal(d+1, maxInd+1, j, ar, index, ans);
        
    }


    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();
        }

    }
}