import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;

public class TestsGen {

    static Random rnd = new Random(4);
    static final int[] DX = new int[] {0, 1, 0, -1};
    static final int[] DY = new int[] {1, 0, -1, 0};

    static final int[] DX2 = new int[] {-1, -1, -1, 0, 1, 1, 1, 0};
    static final int[] DY2 = new int[] {-1, 0, 1, 1, 1, 0, -1, -1};

    static class Point {
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        static Point random(int x, int y) {
            return new Point(rnd.nextInt(x), rnd.nextInt(y));
        }
    }

    static boolean inBounds(int x, int n) {
        return 0 <= x && x < n;
    }

    static Point[] randomPoints(int n, int x, int y) {
        Point[] res = new Point[n];
        for (int i = 0; i < n; i++) {
            res[i] = Point.random(x, y);
        }
        return res;
    }

    static int[] randInts(int n, int x) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = rnd.nextInt(x);
        }
        return a;
    }

    static class TestWriter {
        int tests;
        String pathPrefix;

        TestWriter(String pathPrefix) {
            this.pathPrefix = pathPrefix;
            File f = new File(pathPrefix);
            if (!f.exists()) {
                System.err.println("Creating directory \"" + pathPrefix + "\"");
                f.mkdir();
            }
            tests = 0;
        }

        void out(Test t) throws FileNotFoundException {
            tests++;
            String fname = pathPrefix + "/" + String.format("%02d", tests);
            System.err.println(fname);
            PrintWriter out = new PrintWriter(fname);
            out.println(t.a.length + " " + t.a[0].length);
            for (int[] a : t.a) {
                for (int i = 0; i < a.length; i++) {
                    out.print(a[i]);
                    if (i < a.length - 1) {
                        out.print(" ");
                    }
                }
                out.println();
            }
            out.close();
        }
    }

    static class Test {
        int[][] a;

        Test(final int[][] a) {
            this.a = new int[a.length][];
            for (int i = 0; i < a.length; i++) {
                this.a[i] = a[i].clone();
            }
        }

        Test shuffleIDs() {
            HashSet<Integer> ids = new HashSet<>();
            for (int[] b : a) {
                for (int i : b) {
                    ids.add(i);
                }
            }
            ArrayList<Integer> oldIDs = new ArrayList<>(ids);
            ArrayList<Integer> newIDs = new ArrayList<>(ids);
            Collections.shuffle(newIDs, rnd);
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < oldIDs.size(); i++) {
                map.put(oldIDs.get(i), newIDs.get(i));
            }
            int[][] newA = new int[a.length][a[0].length];
            for (int i= 0; i < a.length; i++) {
                for (int j = 0; j < a[i].length; j++) {
                    newA[i][j] = map.get(a[i][j]);
                }
            }
            return new Test(newA);
        }

        Test noise(double p, int maxC) {
            int[][] aa = new int[a.length][];
            for (int i = 0; i < a.length; i++) {
                aa[i] = a[i].clone();
                for (int j = 0; j < aa[i].length; j++) {
                    if (rnd.nextDouble() < p) {
                        aa[i][j] = rnd.nextInt(maxC - 1) + 1;
                    }
                }
            }
            return new Test(aa);
        }
    }

    static Test prelimTest1() {
        return  new Test(new int[][] {
                {1, 1, 2, 2, 1},
                {1, 2, 2, 1, 1},
                {1, 2, 3, 3, 1},
                {1, 3, 3, 2, 4},
                {1, 2, 2, 4, 1},
        });
    }

    static Test voronoiManhattan(int n, int m, Point[] initial) {
        return voronoi(DX, DY, n, m, initial);
    }

    static Test voronoi8(int n, int m, Point[] initial) {
        return voronoi(DX2, DY2, n, m, initial);
    }

    static Test voronoi(int[] DX, int[] DY, int n, int m, Point[] initial) {
        int[][] a = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(a[i], -1);
        }
        Queue<Point> q = new ArrayDeque<>();
        for (int i = 0; i < initial.length; i++) {
            Point p = initial[i];
            a[p.x][p.y] = i + 1;
            q.add(p);
        }
        while (!q.isEmpty()) {
            Point p = q.poll();
            for (int dir = 0; dir < DX.length; dir++) {
                int x2 = p.x + DX[dir];
                int y2 = p.y + DY[dir];
                if (!inBounds(x2, n) || !inBounds(y2, m))
                    continue;
                if (a[x2][y2] != -1)
                    continue;
                a[x2][y2] = a[p.x][p.y];
                q.add(new Point(x2, y2));
            }
        }
        return new Test(a).shuffleIDs();
    }

    static Test fork(int n, int m) {
        int[][] a = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(a[i], -1);
        }
        for (int i = 0; i < n; i++) {
            a[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            if (i % 2 == 1)
                continue;
            for (int j = 0; j < m; j++) {
                a[i][j] = 1;
            }
        }
        int used = 2;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j] == -1)
                    a[i][j] = used++;
            }
        }
        return new Test(a).shuffleIDs();
    }

    static Test twoForks(int n, int m) {
        int[][] a = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(a[i], -1);
        }
        for (int i = 0; i < n; i++){
            a[i][0] = 1;
            a[i][m - 1] = 2;
        }
        for (int i = 0; i < n; i++) {
            if (i % 4 == 0) {
                for (int j = 1; j < m - 1; j++) {
                    a[i][j] = 1;
                }
            } else if (i % 4 == 2) {
                for (int j = 1; j < m - 1; j++) {
                    a[i][j] = 2;
                }
            }
        }
        int used = 3;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j] == -1) {
                    a[i][j] = used++;
                }
            }
        }
        return new Test(a).shuffleIDs();
    }

    static Test twoNonCoicidingForks(int n, int m) {
        int[][] a = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(a[i], -1);
        }
        for (int i = 0; i < n; i++){
            a[i][0] = 1;
            a[i][m - 1] = 2;
        }
        for (int i = 0; i < n; i++) {
            if (i % 4 == 0) {
                for (int j = 1; j < m - 2; j++) {
                    a[i][j] = 1;
                }
            } else if (i % 4 == 2) {
                for (int j = 2; j < m - 1; j++) {
                    a[i][j] = 2;
                }
            }
        }
        int used = 3;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j] == -1) {
                    a[i][j] = used++;
                }
            }
        }
        return new Test(a).shuffleIDs();
    }

    static Test squareGridWithNonMaximalInAnswer(int n, int step) {
        return gridWithNonMaximalsInAnswer(n, n, step, step);
    }

    static Test gridWithNonMaximalsInAnswer(int n, int m, int stepX, int stepY) {
        int[] x = new int[(n - 1) / stepX + 1];
        int[] y = new int[(m - 1) / stepY + 1];
        for (int i = 0; i < x.length; i++) {
            x[i] = i * stepX;
        }
        for (int j = 0; j < y.length; j++) {
            y[j] = j * stepY;
        }
        int[][] a = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(a[i], -1);
        }
        for (int i : x) {
            for (int j = 0; j < m; j++) {
                a[i][j] = 1;
            }
        }
        for (int j : y) {
            for (int i = 0; i < n; i++) {
                a[i][j] = 1;
            }
        }
        ArrayList<Point> cells = new ArrayList<>();
        for (int i = 0; i < x.length - 1; i++) {
            for (int j = 0; j < y.length - 1; j++) {
                cells.add(new Point(i, j));
            }
        }
        Collections.shuffle(cells, rnd);
        int used = 4;
        for (int i = 0; i < 2; i++) {
            Point p = cells.get(cells.size() - 1);
            cells.remove(cells.size() - 1);
            int xL = x[p.x] + 1;
            int xR = x[p.x + 1] - 1;
            int yL = y[p.y] + 1;
            int yR = y[p.y + 1] - 1;
            int c = 2;
            while (xL <= xR && yL <= yR) {
                for (int xx = xL; xx <= xR; xx++) {
                    a[xx][yL] = c;
                    a[xx][yR] = c;
                }
                for (int yy = yL; yy <= yR; yy++) {
                    a[xL][yy] = c;
                    a[xR][yy] = c;
                }
                c = 3 - c;
                xL++;
                xR--;
                yL++;
                yR--;
            }
        }
        used++;
        while (cells.size() >= 3) {
            int bound = used++;
            int inner = used++;
            for (int it = 0; it < 3; it++) {
                Point p = cells.get(cells.size() - 1);
                cells.remove(cells.size() - 1);
                int xL = x[p.x] + 1;
                int xR = x[p.x + 1] - 1;
                int yL = y[p.y] + 1;
                int yR = y[p.y + 1] - 1;
                for (int xx = xL; xx <= xR; xx++) {
                    a[xx][yL] = bound;
                    a[xx][yR] = bound;
                }
                for (int yy = yL; yy <= yR; yy++) {
                    a[xL][yy] = bound;
                    a[xR][yy] = bound;
                }
                used++;
                for (int xx = xL + 1; xx <= xR - 1; xx++) {
                    for (int yy = yL + 1; yy <= yR - 1; yy++) {
                        a[xx][yy] = inner;
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j] == -1) {
                    a[i][j] = used++;
                }
            }
        }
        return new Test(a).shuffleIDs();
    }

    static Test walker(int n, int m, int chainsCnt, int chainLength, double turnProb) {
        int[][] a = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(a[i], -1);
        }
        int used = 1;
        for (int it = 0; it < chainsCnt; it++) {
            int x = rnd.nextInt(n);
            int y = rnd.nextInt(m);
            for (int i = 0; i < chainLength;) {
                int dir = rnd.nextInt(DX.length);
                while (true) {
                    int x2 = x + DX[dir];
                    int y2 = y + DY[dir];
                    if (!inBounds(x2, n) || !inBounds(y2, m)) {
                         break;
                    }
                    a[x2][y2] = used;
                    x = x2;
                    y = y2;
                    i++;
                    if (rnd.nextDouble() < turnProb) {
                        break;
                    }
                }
            }
            used++;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j] == -1) {
                    a[i][j] = used++;
                }
            }
        }
        return new Test(a).shuffleIDs();
    }

    static Test allDifferent(int n, int m) {
        int[][] a = new int[n][m];
        int used = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                a[i][j] = used++;
            }
        }
        return new Test(a).shuffleIDs();
    }

    static Test spiral(int n) {
        int[][] a = new int[n][n];
        int used = 2;
        int step = n - 1;
        int x = 0;
        int y = 0;
        a[0][0] = 1;
        while (step > 0) {
            for (int i = 0; i < step; i++) {
                a[x++][y] = 1;
            }
            for (int i = 0; i < step; i++) {
                a[x][y++] = 1;
            }
            for (int i = 0; i < step; i++) {
                a[x--][y] = 1;
            }
            for (int i = 0; i < step - 2; i++) {
                a[x][y--] = 1;
            }
            a[x++][y] = 1;
            a[x++][y] = 1;
            step -= 4;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (a[i][j] == 0)
                    a[i][j] = used++;
            }
        }
        return new Test(a).shuffleIDs();
    }

    static Test twoSpirals(int n) {
        int[][] a = new int[n][n];
        int used = 2;
        int step = n - 1;
        int x = 0;
        int y = 0;
        a[0][0] = 1;
        while (step > 0) {
            for (int i = 0; i < step; i++) {
                a[x++][y] = 1;
            }
            for (int i = 0; i < step; i++) {
                a[x][y++] = 1;
            }
            for (int i = 0; i < step; i++) {
                a[x--][y] = 1;
            }
            for (int i = 0; i < step - 2; i++) {
                a[x][y--] = 1;
            }
            a[x++][y] = 1;
            a[x++][y] = 1;
            step -= 4;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (a[i][j] == 0)
                    a[i][j] = used;
            }
        }
        return new Test(a).shuffleIDs();
    }

    static Test chess(int n, int m) {
        int[][] a = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                a[i][j] = (i + j) % 2 + 1;
            }
        }
        return new Test(a);
    }

    static Test blank(int n, int m) {
        int[][] a = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(a[i], 1);
        }
        return new Test(a);
    }

    static Test serpinski(int n, int m) {
        int[][] a = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                a[i][j] = (i & j) + 1;
            }
        }
        return new Test(a).shuffleIDs();
    }

    static Test twoColoredSnake(int n, int m) {
        int[][] a = new int[n][m];
        int x = 0;
        int y = 0;
        int c = 1;
        for (int i = 0; i < m / 4; i++) {
            for (int j = 0; j < n - 1; j++) {
                a[x++][y] = c = 3 - c;
            }
            a[x][y++] = c = 3 - c;
            a[x][y++] = c = 3 - c;
            for (int j = 0; j < n - 1; j++) {
                a[x--][y] = c = 3 - c;
            }
            a[x][y++] = c = 3 - c;
            a[x][y++] = c = 3 - c;
        }
        int used = 3;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j] == 0) {
                    a[i][j] = used++;
                }
            }
        }
        return new Test(a);
    }

    static Test randomTest(int n, int m, int c) {
        int[][] a = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                a[i][j] = rnd.nextInt(c) + 1;
            }
        }
        return new Test(a);
    }

    static Test[] fromList(ArrayList<Test> tests) {
        Test[] res = new Test[tests.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = tests.get(i);
        }
        return res;
    }

    static Test[] smallTests() {
        final int MAXN = 20;
        ArrayList<Test> tests = new ArrayList<>();
        tests.add(new Test(new int[][]{{1}}));
        tests.add(new Test(new int[][]{{1, 1}, {1, 1}}));
        tests.add(randomTest(MAXN, MAXN, 3));
        tests.add(randomTest(MAXN, MAXN, 4));
        tests.add(randomTest(MAXN, MAXN, 5));
        tests.add(serpinski(MAXN, MAXN));
        tests.add(spiral(MAXN));
        tests.add(twoForks(MAXN, MAXN));
        tests.add(allDifferent(MAXN, MAXN));
        tests.add(twoColoredSnake(MAXN, MAXN));
        return fromList(tests);
    }

    static Test[] mediumTests() {
        final int MAXN = 80;
        ArrayList<Test> tests = new ArrayList<>();
        tests.add(fork(MAXN, MAXN));
        tests.add(twoForks(MAXN, MAXN));
        tests.add(voronoiManhattan(MAXN, MAXN, randomPoints(30, MAXN, MAXN)));
        tests.add(squareGridWithNonMaximalInAnswer(MAXN, (MAXN - 1) / 8));
        tests.add(walker(MAXN, MAXN, MAXN / 3, 12 * MAXN, 3. / MAXN));
        tests.add(allDifferent(MAXN, MAXN));
        tests.add(spiral(MAXN));
        tests.add(twoSpirals(MAXN));
        tests.add(serpinski(MAXN, MAXN));
        tests.add(voronoiManhattan(MAXN, MAXN, randomPoints(MAXN, MAXN, MAXN)));
        tests.add(twoColoredSnake(MAXN, MAXN));
        tests.add(twoNonCoicidingForks(MAXN, MAXN));
        tests.add(randomTest(MAXN, MAXN, 3));
        tests.add(randomTest(MAXN, MAXN, 4));
        tests.add(randomTest(MAXN, MAXN, 5));
        int n = tests.size();
        for (int i = 0; i < n; i++) {
            tests.add(tests.get(i).noise(0.1, 100000));
        }
        return fromList(tests);
    }

    static Test[] largeTests() {
        final int MAXN = 1000;
        ArrayList<Test> tests = new ArrayList<>();
        tests.add(fork(MAXN, MAXN));
        tests.add(twoForks(MAXN, MAXN));
        tests.add(voronoiManhattan(MAXN, MAXN, randomPoints(30, MAXN, MAXN)));
        tests.add(voronoi8(MAXN, MAXN, randomPoints(30, MAXN, MAXN)));
        tests.add(squareGridWithNonMaximalInAnswer(MAXN, (MAXN - 1) / 8));
        tests.add(squareGridWithNonMaximalInAnswer(MAXN, (MAXN - 1) / 20));
        tests.add(squareGridWithNonMaximalInAnswer(MAXN, (MAXN - 1) / 4));
        tests.add(walker(MAXN, MAXN, MAXN / 3, 12 * MAXN, 3. / MAXN));
        tests.add(allDifferent(MAXN, MAXN));
        tests.add(spiral(MAXN));
        tests.add(twoSpirals(MAXN));
        tests.add(chess(MAXN, MAXN));
        tests.add(serpinski(MAXN, MAXN));
        tests.add(blank(MAXN, MAXN));
        tests.add(voronoiManhattan(MAXN, MAXN, randomPoints(MAXN, MAXN, MAXN)));
        tests.add(twoColoredSnake(MAXN, MAXN));
        tests.add(twoNonCoicidingForks(MAXN, MAXN));
        tests.add(randomTest(MAXN, MAXN, 3));
        tests.add(randomTest(MAXN, MAXN, 4));
        tests.add(randomTest(MAXN, MAXN, 5));
        int n = tests.size();
        for (int i = 0; i < n; i++) {
            tests.add(tests.get(i).noise(0.1, 100000));
        }
        return fromList(tests);
    }

    public static void main(String[] args) throws IOException {
        TestWriter prelim = new TestWriter("../preliminary");
        prelim.out(prelimTest1());
        TestWriter tests = new TestWriter("../tests");
        System.err.println("Generating small tests");
        for (Test t : smallTests()) {
            tests.out(t);
        }
        System.err.println("Generating medium tests");
        for (Test t : mediumTests()) {
            tests.out(t);
        }
        System.err.println("Generating large tests");
        for (Test t : largeTests()) {
            tests.out(t);
        }
    }

}
