import javafx.util.Pair;

import java.io.*;
import java.util.*;

public class TestGen {
    int testCount;
    PrintWriter testsDesc;
    static Random random = new Random(787788);
    static final int MAX_N = 1_000_000_000;
    static final int MAX_M = 100_000;

    // cinema nxn
    // k friends
    // k+1 points: k points for occupied places and 1 point for best place
    class Test {
        int n, k;
        int[] x;
        int[] y;

        Test() {}
        Test(int n, int k, int[] x, int[] y) {
            this.n = n;
            this.k = k;
            this.x = x;
            this.y = y;
        }
    }

    Test[] samples = {
            new Test(3, 2, new int[]{1, 1}, new int[]{2, 1}),
            new Test(3, 2, new int[]{1, 2, 3, 2}, new int[]{2, 2, 2, 2})
    };

    void write(Test t) throws IOException {
        String path = String.format("../tests/%02d", ++testCount);
        PrintWriter out = new PrintWriter(path);
        out.println(t.n + " " + (t.x.length - 1) + " " + t.k);
        for (int i = 0; i < t.x.length; i++) {
            out.println(t.x[i] + " " + t.y[i]);
        }
        out.close();
        System.out.println(String.format("Test %d is generated", testCount));
    }

    void genHand(Test[] a) throws IOException {
        for (Test test : a) {
            write(test);
        }
    }

    void genMaxAns() throws IOException {
        int n = MAX_N;
        int k = MAX_N;
        int x[] = new int[MAX_M + 1];
        int y[] = new int[MAX_M + 1];
        for (int i = 0; i < MAX_M; i++) {
            x[i] = i + 1;
            y[i] = 1;
        }
        x[MAX_M] = 1;
        y[MAX_M] = 1;
        write(new Test(n, k, x, y));
    }

    void genSomeStrangeTest(int n, int m, int k) throws IOException {
        int x[] = new int[m + 1];
        int y[] = new int[m + 1];
        x[m] = random.nextInt(n / 2) + n / 4;
        y[m] = random.nextInt(n / 2) + n / 4;
        for (int i = 0; i < m / 4; i++) {
            x[i] = x[m] - i;
            y[i] = y[m];
        }
        for (int i = m / 4; i < m / 2; i++) {
            x[i] = x[m] + (i - m / 4) + 1;
            y[i] = y[m];
        }
        for (int i = m / 2; i < m / 2 + m / 4; i++) {
            x[i] = x[m];
            y[i] = y[m] + (i - m / 2 + 1) * k;
        }
        for (int i = m / 2 + m / 4; i < 3 * m / 4; i++) {
            x[i] = x[m];
            y[i] = y[m] - (i - m / 2 - m / 4 + 1) * k;
        }

        TreeSet<Integer[]> set = new TreeSet<Integer[]>(new Comparator<Integer[]>() {
            @Override
            public int compare(Integer o1[], Integer o2[]) {
                if (o1[0].compareTo(o2[0]) != 0) {
                    return Integer.compare(o1[0], o2[0]);
                }
                return Integer.compare(o1[1], o2[1]);
            }
        });
        for (int i = 0; i < 3 * m / 4; i++) {
            set.add(new Integer[]{x[i], y[i]});
        }
        for (int i = 3 * m / 4; i < m; i++) {
            int K = (int)(Math.sqrt(m / 2));
            int c1 = random.nextInt(2 * K) - K;
            int c2 = random.nextInt(2 * K) - K;
            if (c1 == 0) {
                i--;
                continue;
            }
            c1 = x[m] + c1;
            c2 = y[m] + c2 * k;
            x[i] = c1;
            y[i] = c2;
            if (set.contains(new Integer[]{x[i], y[i]})) {
                i--;
                continue;
            }
            set.add(new Integer[]{x[i], y[i]});
        }

        write(new Test(n, k, x, y));
    }

    long getSum(int k) {
        // 1+2+...+k
        return (long)k * (k + 1) / 2;
    }

    void genAwayFromCenter(int n, int m, int k) throws IOException {
        assert m <= (long)n * n;
        TreeSet<Pair<Long, Pair<Integer, Integer>>> set = new TreeSet<>();
        int x[] = new int[m + 1];
        int y[] = new int[m + 1];
        x[m] = random.nextInt(n) + 1;
        y[m] = random.nextInt(n - k / 2 * 2) + k / 2 + 1;
        long costMid = getSum((k - 1) / 2) + getSum((k - 1) - (k - 1) / 2);
        set.add(new Pair<>(costMid, new Pair<>(x[m], y[m])));
        int cur = 0;
        TreeSet<Pair<Integer, Integer>> was = new TreeSet<>();
        while (cur < m) {
            if (set.isEmpty()) {
                while (cur < m) {
                    int xx = random.nextInt(n) + 1;
                    int yy = random.nextInt(n) + 1;
                    x[cur] = xx;
                    y[cur] = yy;
                    if (was.contains(new Pair<>(x[cur], y[cur]))) continue;
                    was.add(new Pair<>(x[cur], y[cur]));
                    cur++;
                }
                break;
            }
            Pair<Long, Pair<Integer, Integer>> o = set.pollFirst();
            Pair<Integer, Integer> cell = o.second;
            x[cur] = cell.first;
            y[cur] = cell.second;
            was.add(new Pair<>(x[cur], y[cur]));
            cur++;
            if (cell.second.equals(y[m])) {
                if (cell.first >= x[m] && cell.first < n) {
                    set.add(new Pair<>(costMid + (long)(cell.first + 1 - x[m]) * k, new Pair<>(cell.first + 1, cell.second)));
                }
                if (cell.first <= x[m] && cell.first > 1) {
                    set.add(new Pair<>(costMid + (long)(x[m] - (cell.first - 1)) * k, new Pair<>(cell.first - 1, cell.second)));
                }
                if (cell.second + k <= n) {
                    set.add(new Pair<>((long)(Math.abs(x[m] - cell.first)) * k + getSum(k), new Pair<>(cell.first, cell.second + k)));
                }
                if (cell.second - k >= 1) {
                    set.add(new Pair<>((long)(Math.abs(x[m] - cell.first)) * k + getSum(k), new Pair<>(cell.first, cell.second - k)));
                }
            } else {
                int ny = cell.second + k * (cell.second - y[m]) / Math.abs(cell.second - y[m]);
                if (ny >= 1 && ny <= n) {
                    set.add(new Pair<>(o.first + (long)k * k, new Pair<>(cell.first, ny)));
                }
            }
        }
        write(new Test(n, k, x, y));
    }

    void run() throws IOException {
        new File("../tests").mkdir();

        genHand(samples);
        genAwayFromCenter(10, 10, 4);
        genAwayFromCenter(10, 21, 5);
        genAwayFromCenter(7, 7, 3);
        genSomeStrangeTest(100, 10, 4);
        genMaxAns();
        genSomeStrangeTest(MAX_N, MAX_M, 16);
        genSomeStrangeTest(MAX_N, MAX_M, 100);
        genAwayFromCenter(MAX_N - 5, MAX_M, 999_997);
        genAwayFromCenter(MAX_N - 1, MAX_M, 1_000_000);
        genAwayFromCenter(MAX_N, MAX_M, 100);
        genAwayFromCenter(MAX_N, 111, 7);
        genAwayFromCenter(MAX_N, MAX_M, 13);
    }

    public static void main(String[] args) throws IOException {
        new TestGen().run();
    }

    class Pair<K, V> implements Comparable<Pair<K, V>> {
        final K first;
        final V second;

        Pair(final K first, final V second) {
            this.first = first;
            this.second = second;
        }

        @Override
        public int compareTo(Pair<K, V> o) {
            int x = ((Comparable<K>)first).compareTo(o.first);
            if (x != 0) {
                return x;
            }
            return ((Comparable<V>)second).compareTo(o.second);
        }
    }
}