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(3);
    final static long MAXN = 1000000000;
    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.print(t);
            out.close();
        }
    }

    static class Test {
        int[] w1;
        int[] a, b, w;

        Test(int[] w1, int[] a, int[] b, int[] w) {
            this.w1 = w1.clone();
            this.a = a.clone();
            this.b = b.clone();
            this.w = w.clone();
        }


        @Override
        public String toString() {
            StringBuilder out = new StringBuilder();
            out.append(w1.length / 2);
            out.append("\n");
            for (int i = 0; i < w1.length; i++) {
                out.append(w1[i]);
                if (i != w1.length - 1) {
                    out.append(" ");
                } else {
                    out.append("\n");
                }
            }
            out.append(a.length);
            out.append("\n");
            for (int i = 0; i < a.length; i++) {
                out.append(a[i] + " " + b[i] + " " + w[i] + "\n");
            }
            return out.toString();
        }
    }

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

    static Test randomTest(int n, int q, int maxk) {
        int[] w1 = new int[2 * n];
        for (int i = 0; i < w1.length; i++) {
            w1[i] = rnd.nextInt(maxk);
        }
        int[] a = new int[q];
        int[] b = new int[q];
        int[] w = new int[q];
        for (int i = 0; i < q; i++) {
            do {
                if (rnd.nextBoolean()) {
                    a[i] = 0;
                    b[i] = rnd.nextInt(n) + 1;
                } else {
                    int p = rnd.nextInt(2 * n);
                    a[i] = getFirst(n, p);
                    b[i] = getSecond(n, p);
                }
            } while (a[i] == b[i]);
            w[i] = rnd.nextInt(maxk);
        }
        return new Test(w1, a, b, w);
    }

    static Test frequentFullSequenceRandom(int n, int q) {
        int[] w = new int[2 * n];
        q -= q % 2;
        int[] a = new int[q];
        int[] b = new int[q];
        int[] dw = new int[q];
        for (int i = 0; i < n; i++) {
            w[i] = 2 * q;
            w[i + n] = 2 * q;
        }
        for (int i = 0; i < q; i++) {
            int p = rnd.nextInt(n);
            int p2 = (p + 1) % n;
            a[i] = p + 1;
            b[i] = p2 + 1;
            dw[i] = q - i;
        }
        return new Test(w, a, b, dw);
    }

    static Test frequentFullSequenceFarNonMinimal(int n, int q) {
        int[] w = new int[2 * n];
        q -= q % 2;
        int[] a = new int[q];
        int[] b = new int[q];
        int[] w1 = new int[q];
        for (int i = 0; i < n; i++) {
            w[i] = 10 * n;
            w[i + n] = 0;
        }
        for (int i = 0; i < q; i += 2) {
            a[i] = 1;
            b[i] = 2;
            w1[i] = i;
            i++;
            a[i] = n / 2;
            b[i] = n / 2 + 1;
            w1[i] = i;
            i--;
        }
        return new Test(w, a, b, w1);
    }

    static int getFirst(int n, int i) {
        if (i < n) {
            return 0;
        } else {
            return i - n + 1;
        }
    }

    static int getSecond(int n, int i) {
        if (i < n) {
            return i + 1;
        } else {
            return (i - n + 1) % n + 1;
        }
    }

    static Test randomDecreasing(int n, int q, int maxk) {
        int[] w = new int[2 * n];
        int[] a = new int[q];
        int[] b = new int[q];
        int[] dw = new int[q];
        for (int i = 0; i < 2 * n; i++) {
            w[i] = maxk;
        }
        int[] cw = w.clone();
        for (int i = 0; i < q; i++) {
            int p = rnd.nextInt(2 * n);
            a[i] = getFirst(n, p);
            b[i] = getSecond(n, p);
            int d = cw[p] + maxk;
            int sub = rnd.nextInt(d);
            dw[i] = cw[p] - d;
            cw[p] = w[i];
        }
        return new Test(w, a, b, dw);
    }

    static Test flip(Test t) {
        for (int i = 0; i < t.w.length; i++) {
            t.w[i] = -t.w[i];
        }
        for (int i = 0; i < t.w1.length; i++) {
            t.w1[i] = -t.w1[i];
        }
        return t;
    }

    static Test randomIncreasing(int n, int q, int maxk) {
        return flip(randomDecreasing(n, q, maxk));
    }

    static Test killRandomEdges(int n, int q, int maxk) {
        int[] w = new int[2 * n];
        int[] a = new int[q];
        int[] b = new int[q];
        int[] dw = new int[q];
        for (int i = 0; i < q; i++) {
            int p = rnd.nextInt(2 * n);
            a[i] = getFirst(n, p);
            b[i] = getSecond(n, p);
            dw[i] = maxk;
        }
        return new Test(w, a, b, dw);
    }

    static Test releaseRandomEdges(int n, int q, int maxk) {
        return flip(killRandomEdges(n, q, maxk));
    }

    static Test releaseAllOnBoundRand(int n) {
        int[] w = new int[2 * n];
        int[] a = new int[n];
        int[] b= new int[n];
        int[] w1 = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = n;
            w[i + n] = n + 1;
        }
        ArrayList<Integer> perm = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            perm.add(i + 1);
        }
        Collections.shuffle(perm, rnd);
        for (int i = 0; i < n; i++) {
            a[i] = perm.get(i);
            b[i] = a[i] % n + 1;
            w1[i] = n - i;
        }
        return new Test(w, a, b, w1);
    }

    static Test releaseAllOnBoundAnotherOrder(int n) {
        int[] w = new int[2 * n];
        int[] a = new int[n];
        int[] b= new int[n];
        int[] w1 = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = n;
            w[i + n] = n + 1;
        }
        ArrayList<Integer> perm = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            perm.add(i + 1);
        }
        Collections.sort(perm, new Comparator<Integer>() {
            @Override
            public int compare(Integer i1, Integer i2) {
                return Integer.numberOfTrailingZeros(i1) - Integer.numberOfTrailingZeros(i2);
            }
        });
        for (int i = 0; i < n; i++) {
            a[i] = perm.get(i);
            b[i] = a[i] % n + 1;
            w1[i] = n - i;
        }
        return new Test(w, a, b, w1);
    }



    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<>();
        int[] nS = new int[]{3, 3, 3, 3, 4, 5, 6, 10, 20, 30, 50, 100, 1000, 10000, 100000};
        for (int i : nS) {
            tests.add(randomTest(i, 0, (int)Math.min(i * (long) i, MAXN)));
        }
        return fromList(tests);
    }

    static Test[] mediumTests() {
        ArrayList<Test> tests = new ArrayList<>();
        int[] nS = new int[]{3, 10, 100, 1000};
        for (int n : nS) {
            for (int q : nS) {
                tests.add(randomTest(n, q, (int)Math.min(n * (long) q, MAXN)));
            }
        }
        return fromList(tests);
    }

    static Test[] largeTests() {
        final int MAXN = 100000;
        final int MAXK = 1000000000;
        ArrayList<Test> tests = new ArrayList<>();
        tests.add(randomDecreasing(MAXN, MAXN, MAXK));
        tests.add(randomIncreasing(MAXN, MAXN, MAXK));
        tests.add(frequentFullSequenceRandom(MAXN, MAXN));
        tests.add(flip(frequentFullSequenceRandom(MAXN, MAXN)));
        tests.add(killRandomEdges(MAXN, MAXN, MAXK));
        tests.add(releaseRandomEdges(MAXN, MAXN, MAXK));
        tests.add(frequentFullSequenceFarNonMinimal(MAXN, MAXN));
        tests.add(flip(frequentFullSequenceFarNonMinimal(MAXN, MAXN)));
        tests.add(randomTest(MAXN, MAXN, MAXK));
        tests.add(releaseAllOnBoundRand(MAXN));
        tests.add(flip(releaseAllOnBoundRand(MAXN)));
        tests.add(releaseAllOnBoundAnotherOrder(MAXN));
        tests.add(flip(releaseAllOnBoundAnotherOrder(MAXN)));
        tests.add(randomTest(MAXN, MAXN, MAXK));
        tests.add(randomTest(MAXN, MAXN, MAXK));
        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);
        }
    }

}
