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

public class GameTestGen {

	final int MAX_N = 100_000;
	final int MAX_M = 100_000;
	final static Random rng = new Random("game".hashCode());

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

	PrintWriter out;
	int countTests = 0;

	void generate() {
		createTestsDir();
		generateSamples();

		generateSmall();
		printAll();
		generateMedium();
		printAll();
		generateLarge();
		printAll();
	}

	List<TestCase> allTests = new ArrayList<>();

	private void generateSamples() {
		TestCase sample1 = new TestCase(4, 3, 1, new int[] { 3, 2, 1, 2 });
		TestCase sample2 = new TestCase(1, 2, 1, new int[] { 2 });
		TestCase sample3 = new TestCase(5, 5, 2, new int[] { 4, 2, 1, 4, 3 });
		printTest(Arrays.asList(sample1, sample2, sample3));
	}

	private void generateSmall() {
		// test 4
		allTests.add(new TestCase(1, 1, 1, new int[] { 1 }));

		// tests 5-8
		allTests.add(new TestCase(2, 1, 1, new int[] { 1, 1 }));
		allTests.add(new TestCase(2, 2, 1, new int[] { 1, 2 }));
		allTests.add(new TestCase(2, 2, 1, new int[] { 2, 1 }));
		allTests.add(new TestCase(2, 2, 2, new int[] { 2, 1 }));

		// tests 9-15
		allTests.add(new TestCase(3, 2, 1, new int[] { 2, 1, 2 }));
		allTests.add(new TestCase(3, 3, 1, new int[] { 1, 2, 3 }));
		allTests.add(new TestCase(3, 3, 1, new int[] { 3, 1, 2 }));
		allTests.add(new TestCase(3, 2, 3, new int[] { 1, 1, 1 }));

		allTests.add(new TestCase(3, 3, 2, new int[] { 3, 1, 2 }));
		allTests.add(new TestCase(3, 3, 2, new int[] { 3, 2, 1 }));
		allTests.add(new TestCase(3, 3, 3, new int[] { 3, 2, 1 }));

		// tests 16-20
		allTests.add(new TestCase(2, new int[] { 3, 2, 1, 2 }));
		allTests.add(new TestCase(7, 5, 2, new int[] { 3, 2, 1, 3, 1, 2, 2 }));

		int n = 10;
		allTests.add(new TestCase(n, n, 1, rangeDesc(n, 1)));
		allTests.add(new TestCase(n, n, 1, randomArray(n, n)));
		allTests.add(new TestCase(n, MAX_M, n, randomArray(n, n)));

		for (n = 8; n <= 10; n++) {
			for (int max = 3; max <= 6; max++) {
				for (int IT = 0; IT < 2000; IT++) {
					TestCase test = new TestCase(randRange(1, n / 2),
							randomArray(n, max));
					allTests.add(test);
				}
			}
			for (int IT = 0; IT < 2000; IT++) {
				TestCase test = new TestCase(randRange(1, n / 2),
						randomPermutation(n));
				allTests.add(test);
			}
		}

		for (n = 11; n <= 15; n++) {
			for (int max = 4; max <= 8; max++) {
				for (int IT = 0; IT < 1000; IT++) {
					TestCase test = new TestCase(randRange(1, n / 2),
							randomArray(n, max));
					allTests.add(test);
				}
			}
			for (int IT = 0; IT < 1000; IT++) {
				TestCase test = new TestCase(randRange(1, n / 2),
						randomPermutation(n));
				allTests.add(test);
			}
		}
	}

	private void generateMedium() {
		int n = 1000;

		{ // test 21
			int k = 100;
			TestCase tc = new TestCase(k, concat(rangeAsc(k + 1, n),
					rangeAsc(1, k)));
			allTests.add(tc);
		}

		{ // test 22
			int k = 200;
			TestCase tc = new TestCase(k, concat(rangeAsc(k + 1, n),
					rangeDesc(k, 1)));
			allTests.add(tc);
		}

		{ // test 23
			int k = 300;
			TestCase tc = new TestCase(k, concat(rangeAsc(k + 1, n),
					rangeAsc(1, k)));
			allTests.add(tc);
		}

		{ // test 24
			int k = 400;
			TestCase tc = new TestCase(k, rangeAsc(1, n));
			allTests.add(tc);
		}

		{ // test 25
			int k = 50;
			TestCase tc = new TestCase(k, rangeDesc(n, 1));
			allTests.add(tc);
		}

		{ // test 26
			int k = randRange(50, 100);
			int[] a = new int[n];

			for (int i = 0; i < n; i++) {
				a[i] = i / k * k + (k - i % k);
			}
			TestCase tc = new TestCase(k, a);
			allTests.add(tc);
		}

		{ // test 27
			int k = 500;
			TestCase tc = new TestCase(k, concat(rangeDesc(k + 1, 2),
					rangeAsc(1, k)));
			allTests.add(tc);
		}

		{ // test 28
			int k = 2;
			TestCase tc = new TestCase(k, concat(new int[] { n },
					rangeAsc(1, n - 1)));
			allTests.add(tc);
		}

		{ // test 29
			int k = randRange(1, 10);
			TestCase tc = new TestCase(k, concat(rangeAsc(n - k + 1, n),
					rangeAsc(1, n - k)));
			allTests.add(tc);
		}

		{ // test 30
			int k = 100;
			int[] ar = concat(rangeDesc(k + 1, 1), rangeDesc(2 * k, k + 1),
					repeat(2, n - 2 * k - 1));
			TestCase tc = new TestCase(k, ar);
			allTests.add(tc);
		}

		{
			n = 100;
			for (int IT = 0; IT < 5000; IT++) {
				int mx = randRange(1, 20);
				allTests.add(new TestCase(randRange(1, mx), randomArray(n, mx)));
				allTests.add(new TestCase(randRange(1, 10),
						randomPermutation(n)));
			}
		}

		{
			n = 1000;
			for (int IT = 0; IT < 200; IT++) {
				int mx = randRange(1, 50);
				allTests.add(new TestCase(randRange(1, mx), randomArray(n, mx)));
				allTests.add(new TestCase(randRange(1, 20),
						randomPermutation(n)));
			}
		}
	}

	private void generateLarge() {
		int n = 100000, m = 100000;
		List<TestCase> largeTests = new ArrayList<>();

		{ // test 31
			int k = randRange(n / 2, n);
			largeTests.add(new TestCase(k, concat(rangeAsc(k + 1, n),
					rangeAsc(1, k))));
		}

		{ // test 32
			int k = randRange(n / 10, n / 2);
			largeTests.add(new TestCase(k, concat(rangeAsc(k + 1, n),
					rangeDesc(k, 1))));
		}

		{ // test 33
			int k = randRange(n / 2, n);
			largeTests.add(new TestCase(k, concat(rangeAsc(k + 1, n),
					rangeAsc(1, k))));
		}

		{ // test 34
			int k = randRange(1, n / 100);
			largeTests.add(new TestCase(k, rangeAsc(1, n)));
		}

		{ // test 35
			int k = 4;
			int[] a = concat(repeat(n, n - 9), new int[] { 2, 3, 4, 5, 1, 7, 6,
					2, 4 });
			largeTests.add(new TestCase(k, a));
		}

		{ // test 36
			int k = randRange(500, 2000);
			int[] a = new int[n];

			for (int i = 0; i < n; i++) {
				a[i] = Math.min(n, i / k * k + k) - i % k;
			}
			largeTests.add(new TestCase(k, a));
		}

		{ // test 37
			int k = n / 2;
			largeTests.add(new TestCase(k, concat(rangeDesc(k + 1, 2),
					rangeAsc(1, k))));
		}

		{ // test 38
			int k = 2;
			TestCase tc = new TestCase(k, concat(new int[] { n },
					rangeAsc(1, n - 1)));
			largeTests.add(tc);
		}

		{ // test 39
			int k = randRange(1, 100);
			TestCase tc = new TestCase(k, concat(rangeAsc(n - k + 1, n),
					rangeAsc(1, n - k)));
			largeTests.add(tc);
		}

		{ // test 40
			int k = randRange(1000, 2000);
			int[] ar = concat(rangeDesc(k + 1, 1), rangeDesc(2 * k, k + 1),
					repeat(2, n - 2 * k - 1));
			TestCase tc = new TestCase(k, ar);
			largeTests.add(tc);
		}
		// print 31-40

		for (TestCase tc : largeTests) {
			allTests.add(tc);
		}

		// 10 random changes, tests 41-50
		for (int test = 41; test <= 50; test++) {
			TestCase tc = largeTests.get(rng.nextInt(largeTests.size()));
			allTests.add(tc.randomMod(0.005 + (test - 40) * 0.01));
		}

		// kinda max-n corner cases, tests 51-60

		allTests.add(new TestCase(n, m, 1, repeat(1, n)));
		allTests.add(new TestCase(n, m, n, repeat(1, n)));
		allTests.add(new TestCase(n, m, 1, rangeAsc(1, n)));
		allTests.add(new TestCase(n, m, 1, rangeDesc(n, 1)));
		allTests.add(new TestCase(n, m, 1, randomPermutation(n)));
		allTests.add(new TestCase(n, m, n, randomPermutation(n)));
		allTests.add(new TestCase(n, m, 1, randomArray(n, 100)));
		allTests.add(new TestCase(n, m, 1, randomArray(n, 1000)));
		allTests.add(new TestCase(n, m, 1, randomArray(n, n)));
		allTests.add(new TestCase(n - 1, m, n - 1, rangeAsc(2, n)));

		// 5 random tests, 61-65
		for (int test = 61; test <= 65; test++) {
			m = randRange(1, 100);
			int k = randRange(1, m);
			allTests.add(new TestCase(n, m, k, randomArray(n, m)));
		}

	}

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

	int[] concat(int[]... arrays) {
		int len = 0;
		for (int[] a : arrays) {
			len += a.length;
		}
		int[] result = new int[len];
		len = 0;
		for (int[] a : arrays) {
			for (int i = 0; i < a.length; i++) {
				result[i + len] = a[i];
			}
			len += a.length;
		}
		return result;
	}

	int[] repeat(int k, int times) {
		int[] a = new int[times];
		Arrays.fill(a, k);
		return a;
	}

	int[] randomArray(int len, int max) {
		int[] ret = new int[len];
		for (int i = 0; i < len; i++) {
			ret[i] = randRange(1, max);
		}
		return ret;
	}

	int[] rangeAsc(int from, int to) {
		if (from > to) {
			return new int[0];
		}
		int[] ret = new int[to - from + 1];
		for (int i = 0; i < ret.length; i++) {
			ret[i] = from + i;
		}
		return ret;
	}

	int[] rangeDesc(int from, int to) {
		return reverse(rangeAsc(to, from));
	}

	int[] reverse(int[] a) {
		int[] b = a.clone();
		for (int i = 0, j = b.length - 1; i < j; i++, j--) {
			int tmp = b[i];
			b[i] = b[j];
			b[j] = tmp;
		}
		return b;
	}

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

	class TestCase {
		final int n, m, k;
		final int[] a;

		public TestCase randomMod(double prob) {
			int newK = k;
			if (rng.nextDouble() < prob) {
				newK = modWithinRange(newK, -10, 10, 1, n);
			}
			TestCase mod = new TestCase(this.n, this.m, newK, this.a);

			for (int i = 0; i < a.length; i++) {
				if (rng.nextDouble() < prob) {
					mod.a[i] = modWithinRange(mod.a[i], -1, 1, 1, m);
				}
			}
			return mod;
		}

		private int modWithinRange(int old, int min, int max, int L, int R) {
			int val = old + randRange(min, max);
			if (val < L) {
				val = L;
			}
			if (val > R) {
				val = R;
			}
			return val;
		}

		public TestCase(int n, int m, int k, int[] a) {
			this.n = n;
			this.m = m;
			this.k = k;
			this.a = a.clone();
		}

		public TestCase(int k, int[] a) {
			this.a = a.clone();
			this.k = k;
			this.n = a.length;
			this.m = max(a);
		}
	}

	int max(int[] a) {
		int m = 0;
		for (int i : a) {
			m = Math.max(m, i);
		}
		return m;
	}

	void createTestsDir() {
		File testDir = new File("../tests/");
		if (!testDir.exists()) {
			testDir.mkdir();
		}
	}

	void printAll() {
		List<TestCase> curTest = new ArrayList<GameTestGen.TestCase>();
		int sum = 0;

		for (TestCase tc : allTests) {
			if (sum + tc.n > MAX_N) {
				printTest(curTest);
				sum = 0;
				curTest.clear();
			}
			sum += tc.n;
			curTest.add(tc);
		}
		printTest(curTest);

		allTests.clear();
	}

	void printTest(List<TestCase> testCases) {
		try {
			countTests++;
			String fileName = String.format("../tests/%02d", countTests);
			out = new PrintWriter(fileName);

			out.println(testCases.size());
			for (TestCase tc : testCases) {
				out.println(tc.n + " " + tc.m + " " + tc.k);
				printArray(tc.a);
			}

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

	void printArray(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			out.print(arr[i]);
			if (i + 1 == arr.length) {
				out.println();
			} else {
				out.print(" ");
			}
		}
	}
}
