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

public class TestGen {

    final static int MAXN = 300;
    final static int MAXC = 1_000_000;
    static Random rnd = new Random(3);

    static interface Mutator {
        Test mutate(Test t);
    }

    static class RCShuffler implements Mutator {
        final Random rnd;

        public RCShuffler(Random rnd) {
            this.rnd = rnd;
        }

        @Override
        public Test mutate(Test t) {
            int n = t.a.length;
            int m = t.a[0].length;
            ArrayList<Integer> rPerm = new ArrayList<Integer>();
            ArrayList<Integer> cPerm = new ArrayList<Integer>();
            for (int i = 0; i < n; i++) {
                rPerm.add(i);
            }
            for (int j = 0; j < m; j++) {
                cPerm.add(j);
            }
            Collections.shuffle(rPerm, rnd);
            Collections.shuffle(cPerm, rnd);
            int[][] c = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    c[i][j] = t.a[rPerm.get(i)][cPerm.get(j)];
                }
            }
            return new Test(c);
        }
    }

    static class ColorShuffler implements Mutator {
        final Random rnd;

        ColorShuffler(Random rnd) {
            this.rnd = rnd;
        }

        @Override
        public Test mutate(Test t) {
            HashSet<Integer> presentedColors = new HashSet<>();
            for (int[] ax : t.a) {
                for (int a : ax) {
                    presentedColors.add(a);
                }
            }
            HashMap<Integer, Integer> enumeration = new HashMap<>();
            {
                int c = 0;
                for (int x : presentedColors) {
                    enumeration.put(x, c++);
                }
            }
            HashSet<Integer> newRandomColors = new HashSet<>();
            for (int i = 0; newRandomColors.size() < presentedColors.size(); i++) {
                newRandomColors.add(rnd.nextInt(MAXC) + 1);
            }
            ArrayList<Integer> newRandomColorsL = new ArrayList<>(newRandomColors);
            int n = t.a.length;
            int m = t.a[0].length;
            int[][] c = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    c[i][j] = newRandomColorsL.get(enumeration.get(t.a[i][j]));
                }
            }
            return test(c);
        }
    }

    static class Razuplotnitel implements Mutator {
        final int dx, dy;

        Razuplotnitel(int dx, int dy) {
            this.dx = dx;
            this.dy = dy;
        }

        @Override
        public Test mutate(Test t) {
            int n = t.a.length;
            int m = t.a[0].length;
            int[][] c = new int[n * dx][m * dy];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    for (int x = 0; x < dx; x++) {
                        for (int y = 0; y < dy; y++) {
                            c[i * dx + x][j * dy + y] = t.a[i][j];
                        }
                    }
                }
            }
            return new Test(c);
        }
    }

    static Mutator rotate = new Mutator() {
        @Override
        public Test mutate(Test t) {
            int n = t.a.length;
            int m = t.a[0].length;
            int[][] c = new int[m][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    c[m - j - 1][i] = t.a[i][j];
                }
            }
            return test(c);
        }
    };

    static class ZeroToRandom implements Mutator {
        final Random rnd;

        ZeroToRandom(Random rnd) {
            this.rnd = rnd;
        }

        @Override
        public Test mutate(Test t) {
            int n = t.a.length;
            int m = t.a[0].length;
            int[][] c = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (t.a[i][j] == 0) {
                        c[i][j] = rnd.nextInt(MAXC);
                    } else {
                        c[i][j] = t.a[i][j];
                    }
                }
            }
            return test(c);
        }
    }

    static Test unzero(Test t) {
        return new ZeroToRandom(rnd).mutate(t);
    }

    static Test add(Test t1, Test t2) {
        int n = t1.a.length;
        int m = t1.a[0].length;
        if (n != t2.a.length) {
            throw new AssertionError("not equal");
        }
        if (m != t2.a[0].length) {
            throw new AssertionError("not equal");
        }
        int[][] c = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                c[i][j] = t1.a[i][j] + t2.a[i][j];
            }
        }
        return test(c);
    }

    static ArrayList<Integer> zip(ArrayList<Integer>... a) {
        ArrayList<Integer> res = new ArrayList<>();
        int len = a[0].size();
        for (ArrayList<Integer> ax : a) {
            len = Math.min(len, ax.size());
        }
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < a.length; j++) {
                res.add(a[j].get(i));
            }
        }
        return res;
    }

    static interface PermGen {
        int[] perm(int n);
    }

    static class RandomPermGen implements PermGen {
        final Random rnd;

        RandomPermGen(Random rnd) {
            this.rnd = rnd;
        }

        @Override
        public int[] perm(int n) {
            ArrayList<Integer> perm = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                perm.add(i);
            }
            Collections.shuffle(perm, rnd);
            int[] permA = new int[n];
            for (int i = 0; i < n; i++) {
                permA[i] = perm.get(i);
            }
            return permA;
        }
    }

    static PermGen randomPerm = new RandomPermGen(rnd);

    static PermGen idPerm = new PermGen() {
        @Override
        public int[] perm(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = i;
            }
            return a;
        }
    };

    static PermGen idRIdPerm = new PermGen() {
        int id = 0;

        @Override
        public int[] perm(int n) {
            int[] a = new int[n];
            if (id % 4 < 2) {
                for (int i = 0; i < n; i++) {
                    a[i] = i;
                }
            } else {
                for (int i = 0; i < n; i++) {
                    a[i] = n - i - 1;
                }
            }
            id++;
            return a;
        }
    };

    static Test randomSpiral(int n) {
        return genSpiral(randomPerm, n);
    }

    static Test spiral1(int n) {
        return genSpiral(idPerm, n);
    }

    static Test spiral2(int n) {
        return genSpiral(idRIdPerm, n);
    }

    static Test genSpiral(PermGen gen, int n) {
        ArrayList<Integer> uppers = new ArrayList<>();
        ArrayList<Integer> lowers = new ArrayList<>();
        ArrayList<Integer> rights = new ArrayList<>();
        ArrayList<Integer> lefts = new ArrayList<>();
        for (int i = 0; i < n / 2; i++) {
            uppers.add(i + 1);
            lowers.add(n - i);
        }
        for (int i = 0; i < n / 2; i++) {
            lefts.add(-(i + 1));
            rights.add(-(n - i));
        }
        int[][] c = new int[n][n];
        int[][] c2 = new int[n][n];
        int[] cntR = new int[n];
        int[] cntC = new int[n];
        int need = n / 2 + 1;
        for (int b : zip(uppers, rights, lowers, lefts)) {
            if (b > 0) {
                b--;
                int needHere = Math.max(0, need - cntR[b]);

                int[] perm = gen.perm(n);
                for (int j = 0; j < n && needHere > 0; j++) {
                    int jnd = perm[j];
                    if (c2[b][jnd] == 0) {
                        c[b][jnd] = 1;
                        needHere--;
                    }
                }
                for (int j = 0; j < n; j++) {
                    if (c2[b][j] == 0) {
                        c2[b][j] = 1;
                        cntR[b]++;
                        cntC[j]++;
                    }
                }
            } else {
                b = -b - 1;
                int[] perm = gen.perm(n);
                int needHere = Math.max(0, need - cntC[b]);
                for (int i = n - 1; i >= 0 && needHere > 0; i--) {
                    int ind = perm[i];
                    if (c2[ind][b] == 0) {
                        c[ind][b] = 1;
                        needHere--;
                    }
                }
                for (int i = 0; i < n; i++) {
                    if (c2[i][b] == 0) {
                        c2[i][b] = 1;
                        cntR[i]++;
                        cntC[b]++;
                    }
                }
            }
        }
        return test(c);
    }

    static Test thirdBest(int n, int m) {
        int[][] a = new int[n][m];
        for (int i = 0; i < n / 2 + 1; i++) {
            for (int j = 0; j < m / 2 + 1; j++) {
                a[i][j] = 1;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j] == 0) {
                    a[i][j] = rnd.nextInt(2) + 2;
                }
            }
        }
        return test(a);
    }

    static Mutator spoil1percent = new Mutator() {
        @Override
        public Test mutate(Test t) {
            int n = t.a.length;
            int m = t.a[0].length;
            int[][] a = new int[n][];
            for (int i = 0; i < n; i++) {
                a[i] = t.a[i].clone();
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (rnd.nextInt(100) == 0) {
                        a[i][j] = rnd.nextInt(MAXC) + 1;
                    }
                }
            }
            return test(a);
        }
    };

    static Test genXWhites(int n, int m, int lim) {
        int[][] c = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(c[i], 2);
        }
        for (int i = 0; i < lim; i++) {
            int x, y;
            do {
                x = rnd.nextInt(n);
                y = rnd.nextInt(m);
            } while (c[x][y] != 2);
            c[x][y] = 1;
        }
        return test(c);
    }

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

    static Test stripes(int n, int m) {
        int[][] a = new int[n][m];
        for (int i = 0; i < n / 2 + 1; i++) {
            for (int j = 0; j < m / 2 + 1; j++) {
                a[i][j] = 1;
            }
        }
        int c = 2;
        for (int i = n / 2 + 1; i < n; i++) {
            for (int j = 0; j < m / 2 + 1; j++) {
                a[i][j] = c;
            }
            c++;
        }
        for (int j = m / 2 + 1; j < m; j++) {
            for (int i = 0; i < n / 2 + 1; i++) {
                a[i][j] = c;
            }
            c++;
        }
        return unzero(test(a));
    }

    static Test diagonals(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 test(a);
    }

    static Test shuf(Test t) {
        return new RCShuffler(rnd).mutate(t);
    }

    static Test shufC(Test t) {
        return new ColorShuffler(rnd).mutate(t);
    }

    static class TestWriter {
        final String root;
        int tests = 0;

        TestWriter(String path) {
            File root = new File(path);
            if (!root.exists()) {
                System.err.println("Creating directory <" + path + ">");
                root.mkdirs();
            }
            this.root = path;
        }

        void write(Test t) throws FileNotFoundException {
            t = unzero(t);
            String testNo = String.format("%02d", ++tests);
            PrintWriter out = new PrintWriter(root + "/" + testNo);
            System.err.println("Writing test (" + root + ") #" + testNo);
            out.println(t.a.length + " " + t.a[0].length);
            for (int i = 0; i < t.a.length; i++) {
                for (int j = 0; j < t.a[i].length; j++) {
                    out.print(t.a[i][j]);
                    if (j != t.a[i].length - 1) {
                        out.print(" ");
                    }
                }
                out.println();
            }
            out.close();
        }
    }

    static class Test {
        final int[][] a;

        Test(int[][] a) {
            this.a = a;
            for (int[] anA : a) {
                if (anA.length != a[0].length) {
                    throw new AssertionError("non-equal lengths");
                }
            }
        }
    }

    static int[] arr(int... a) {
        return a;
    }

    static Test test(int[]... a) {
        return new Test(a);
    }

    static Test seven3 = test( arr(1, 1, 1, 1, 2, 2, 3)
                             , arr(3, 3, 2, 1, 1, 1, 1)
                             , arr(3, 3, 1, 1, 1, 1, 3)
                             , arr(3, 3, 3, 2, 2, 2, 2)
                             , arr(3, 3, 3, 2, 2, 3, 1)
                             , arr(2, 1, 3, 2, 2, 2, 3)
                             , arr(2, 2, 3, 1, 1, 2, 2));

    public static void main(String[] args) throws FileNotFoundException {
        TestWriter tw = new TestWriter("../tests");
        Test sample1 = test( arr(1, 1, 2)
                           , arr(2, 1, 1)
                           , arr(2, 2, 2));
        tw.write(sample1);
        tw.write(sample1);
        tw.write(test(arr(1, 2), arr(3, 4)));
        tw.write(test(arr(1), arr(2)));
        tw.write(test(arr(1, 2, 1)));
        tw.write(new Razuplotnitel(2, 2).mutate(sample1));
        tw.write(spiral1(7));
        tw.write(spiral2(7));
        tw.write(spiral1(11));
        tw.write(spiral2(11));
        tw.write(randomSpiral(11));
        Test s = spiral2(11);
        Test t1 = shufC(add(shufC(s), rotate.mutate(s)));
        tw.write(t1);
        tw.write(shuf(thirdBest(15, 15)));
        tw.write(seven3);
        tw.write(stripes(9, 9));

        {int[] a = new int[MAXN];
        a[5] = 1;
        tw.write(shufC(test(a)));
        }

        {
            int[][] a = new int[MAXN][1];
            a[10][0] = 1;
            tw.write(shufC(test(a)));
        }


        ArrayList<Test> tests = new ArrayList<Test>() {{
            add(thirdBest(MAXN, MAXN));
            add(spiral1(MAXN));
            add(spiral2(MAXN));
            add(randomSpiral(MAXN));
            add(TestGen.add(shufC(spiral2(MAXN)), rotate.mutate(spiral2(MAXN))));
            add(shufC(TestGen.add(shufC(spiral2(MAXN)), rotate.mutate(spiral2(MAXN)))));
            add(genXWhites(MAXN, MAXN - 1, 1));
            add(genXWhites(MAXN, MAXN, MAXN * MAXN / 2));
            add(genRandom(MAXN, MAXN, 2));
            add(genRandom(MAXN - 1, MAXN, 3));
            add(genRandom(MAXN - 2, MAXN - 1, MAXC));
            add(stripes(MAXN, MAXN));
            add(new Razuplotnitel(MAXN / 7, MAXN / 7).mutate(seven3));
            add(new Razuplotnitel(MAXN / 7, 1).mutate(seven3));
            add(diagonals(MAXN, MAXN));
        }};

        for (Test t : tests) {
            tw.write(t);
        }

        for (Test t : tests) {
            tw.write(shuf(shufC(t)));
        }

        for (Test t : tests) {
            tw.write(spoil1percent.mutate(shuf(shufC(t))));
        }

        tw.write(diagonals(10, 10));
    }
}
