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

public class BattleTestGen {

	static class RandomUtils {
		static double randRange(double from, double to) {
			return from + (to - from) * rng.nextDouble();
		}

		static int randRange(int from, int to) {
			return rng.nextInt(to - from + 1) + from;
		}

		static int[] randomPermutation(int size) {
			int[] a = new int[size];
			for (int i = 1; i < size; i++) {
				a[i] = i;
				int pos = rng.nextInt(i + 1);
				int tmp = a[i];
				a[i] = a[pos];
				a[pos] = tmp;
			}
			return a;
		}

		static int[] randomInversions(int size) {
			int[] a = new int[size];
			for (int i = 0; i < size; i++) {
				a[i] = rng.nextInt(size - i);
			}
			return a;
		}
	}

	final static Random rng = new Random("harlemshake".hashCode());

	public static void main(String[] args) throws Exception {
		new BattleTestGen().generate();
	}

	PrintWriter out;
	boolean isPreliminary;
	int countTests = 0;

	void generate() throws Exception {
		generatePreliminary();
		generateTests();
	}

	void generatePreliminary() {
		isPreliminary = true;
		printTest(new Test(1, new int[] { 3, 0, 2, 1 }));
		printTest(new Test(2, new int[] { 3, 1, 0, 4, 2 }));
	}

	void generateTests() {
		countTests = 0;
		isPreliminary = false;

		generate40();
		generate100();
	}

	// Test group 1: 40 points, tests 1..20
	private void generate40() {
		final int MAX_N = 2000;

		// Tests 1..7, small handy tests
		{
			printTest(new Test(0, new int[] { 0 }));
			printTest(new Test(0, new int[] { 1, 0 }));
			printTest(new Test(1, new int[] { 1, 0 }));
			printTest(new Test(1, new int[] { 0, 1 }));
			printTest(new Test(1, new int[] { 2, 1, 0 }));
			printTest(new Test(2, new int[] { 2, 1, 0 }));
			printTest(new Test(1, new int[] { 1, 2, 0 }));
		}
		// Tests 8..15, random tests with n \in [100..500]
		{
			final int minN = 100, maxN = 500;
			for (int i = 8; i <= 15; i++) {
				randomTest(minN, maxN, 0.25, 0.75);
			}
		}
		// Tests 16..20, handy tests with n = 2000

		{ // 16: random permutation, small k
			int[] perm = RandomUtils.randomPermutation(MAX_N);
			int k = RandomUtils.randRange(50, 300);
			printTest(new Test(k, perm));
		}

		{ // 17: random permutation, large k
			int[] perm = RandomUtils.randomPermutation(MAX_N);
			int k = RandomUtils.randRange(1000, 2000);
			printTest(new Test(k, perm));
		}
		

		{ // 18: reversed perm with some swaps, small k
			int[] perm = worstCase(MAX_N);
			int k = RandomUtils.randRange(50, 300);
			makeSomeSwaps(perm, RandomUtils.randRange(50, 100));
			printTest(new Test(k, perm));
		}
		

		{ // 19: reversed perm with some swaps, large k
			int[] perm = worstCase(MAX_N);
			int k = RandomUtils.randRange(1000, 2000);
			makeSomeSwaps(perm, RandomUtils.randRange(50, 100));
			printTest(new Test(k, perm));
		}
		

		{ // 20: reversed perm, k ~= n
			int[] perm = worstCase(MAX_N);
			int k = RandomUtils.randRange(MAX_N / 2, MAX_N);
			printTest(new Test(k, perm));
		}
		
	}

	// Test group 2: 60 points, tests 21..40, 3 points per test
	private void generate100() {
		final int MAX_N = 200000;
		
		// Tests 21..30: random tests, n \in [50000..150000]
		
		{
			final int minN = 100000, maxN = 150000;
			for (int i = 21; i <= 30; i++) {
				randomTest(minN, maxN, 0.5, 0.9);
			}
		}
		
		// Tests 31..35: handy tests with n ~= 200000, same structure as 16..20
		
		{ // 31: random permutation, small k
			int[] perm = RandomUtils.randomPermutation(MAX_N);
			int k = RandomUtils.randRange(10000, 20000);
			printTest(new Test(k, perm));
		}

		{ // 32: random permutation, large k
			int[] perm = RandomUtils.randomPermutation(MAX_N);
			int k = RandomUtils.randRange(20000, 30000);
			printTest(new Test(k, perm));
		}
		

		{ // 33: reversed perm with some swaps, small k
			int[] perm = worstCase(MAX_N);
			int k = RandomUtils.randRange(10000, 20000);
			makeSomeSwaps(perm, RandomUtils.randRange(10000, 50000));
			printTest(new Test(k, perm));
		}
		

		{ // 34: reversed perm with some swaps, large k
			int[] perm = worstCase(MAX_N);
			int k = RandomUtils.randRange(20000, 30000);
			makeSomeSwaps(perm, RandomUtils.randRange(10000, 50000));
			printTest(new Test(k, perm));
		}
		

		{ // 35: reversed perm, k ~= n
			int[] perm = worstCase(MAX_N);
			int k = RandomUtils.randRange(MAX_N / 2, MAX_N);
			printTest(new Test(k, perm));
		}
		
		// Tests 36..40: n = 200000, handy tests
		
		{ // 36: 2 3 4 ... n 1
			int[] invs = new int[MAX_N];
			invs[0] = MAX_N - 1;
			int[] perm = restore(invs);
			int k = RandomUtils.randRange(20000, 100000);
			printTest(new Test(k, perm));
		}

		{ // 37: 500 blocks [n-400 n-399 ... n-1] [n-800 .. n-401] ... [0 1 ... 399]
			int[] perm = new int[MAX_N];
			for (int i = 0; i < 500; i++) {
				for (int j = 0; j < 400; j++) {
					perm[400 * i + j] = (MAX_N - (i + 1) * 400) + j;
				}
			}
			int k = RandomUtils.randRange(10000, 50000);
			printTest(new Test(k, perm));
		}
		

		{ // 38: 10 blocks
			int[] perm = new int[MAX_N];
			for (int i = 0; i < 10; i++) {
				for (int j = 0; j < 20000; j++) {
					perm[20000 * i + j] = (i + 1) * 20000 - j - 1;
				}
			}
			int k = RandomUtils.randRange(15000, 19000);
			printTest(new Test(k, perm));
		}
		

		{ // 39: reversed, second half mirrored: [199999 199998 ... 100000 0 1 ... 99999]
			int[] perm = new int[MAX_N];
			for (int i = 0; i < MAX_N / 2; i++) {
				perm[i] = MAX_N - 1 - i;
				perm[MAX_N - 1 - i] = MAX_N / 2 - 1 - i;
			}
			int k = RandomUtils.randRange(25000, 40000);
			printTest(new Test(k, perm));
		}
		

		{ // 40: reversed perm, k = n - 2
			int[] perm = worstCase(MAX_N);
			int k = MAX_N - 2;
			printTest(new Test(k, perm));
		}
	}

	private void randomTest(final int minN, final int maxN, final double minRatio, final double maxRatio) {
		int size = RandomUtils.randRange(minN, maxN);
		int[] invs = RandomUtils.randomInversions(size);

		int[] sortedInvs = invs.clone();
		Arrays.sort(sortedInvs);

		double ratio = RandomUtils.randRange(0.25, 0.75);
		int k = sortedInvs[(int) (ratio * size)];

		printTest(new Test(k, restore(invs)));
	}
	
	private void makeSomeSwaps(int[] perm, int swaps) {
		for (int IT = 0; IT < swaps; IT++) {
			int pos1 = RandomUtils.randRange(0, perm.length - 1);
			int pos2 = RandomUtils.randRange(0, perm.length - 1);
			
			int tmp = perm[pos1];
			perm[pos1] = perm[pos2];
			perm[pos2] = tmp;
		}
	}
	
	private int[] worstCase(int size) {
		int[] ans = new int[size];
		for (int i = 0; i < size; i++) {
			ans[i] = size - i - 1;
		}
		return ans;
	}

	private int[] restore(int[] b) {
		int n = b.length;
		SegmentTree tree = new SegmentTree(n);
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			int pos = tree.find(b[i] + 1);
			a[pos] = i;
			tree.set(pos, 0);
		}
		return a;
	}
	
	class SegmentTree {
		int n;
		int[] tree;

		public SegmentTree(int n) {
			this.n = n;
			this.tree = new int[4 * n];
			build(0, n, 0);
		}

		private void build(int l, int r, int i) {
			if (l + 1 == r) {
				tree[i] = 1;
				return;
			}
			int m = (l + r) >> 1;
			build(l, m, 2 * i + 1);
			build(m, r, 2 * i + 2);
			update(i);
		}

		private void update(int i) {
			tree[i] = tree[2 * i + 1] + tree[2 * i + 2];
		}

		public void set(int pos, int val) {
			set(0, n, pos, val, 0);
		}

		private void set(int l, int r, int pos, int val, int i) {
			if (l + 1 == r) {
				tree[i] = val;
				return;
			}
			int m = (l + r) >> 1;
			if (pos < m) {
				set(l, m, pos, val, 2 * i + 1);
			} else {
				set(m, r, pos, val, 2 * i + 2);
			}
			update(i);
		}

		public int find(int value) {
			return find(0, n, value, 0);
		}

		private int find(int l, int r, int value, int i) {
			if (l + 1 == r) {
				return l;
			}
			int m = (l + r) >> 1;
			int sumLeft = tree[2 * i + 1];
			if (sumLeft >= value) {
				return find(l, m, value, 2 * i + 1);
			} else {
				return find(m, r, value - sumLeft, 2 * i + 2);
			}
		}
	}

	class Test {
		int k;
		int[] a;

		public Test(int k, int[] a) {
			super();
			this.k = k;
			this.a = a;
		}

	}

	void printTest(Test test) {
		try {
			countTests++;
			String fileName = (isPreliminary) ? ("../preliminary/")
					: ("../tests/");
			fileName += String.format("%02d", countTests);
			out = new PrintWriter(fileName);

			out.println(test.a.length + " " + test.k);
			for (int i = 0; i < test.a.length; i++) {
				out.print(test.a[i] + 1);
				if (i + 1 == test.a.length) {
					out.println();
				} else {
					out.print(' ');
				}
			}

			System.out.println("Done printing test #" + countTests);
			out.close();
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}
}
