import static java.lang.Math.min;

import java.io.PrintWriter;
import java.util.Random;

public class TestsGen {

	static int testNum = 2;
	static final int MAXN = 100000;

	public static void main(String[] args) {
		// mintest
		genRandom(1, 5, 1, 5);
		genAllOne(1, 5, 1, 5);
		genTwoColor(1, 5, 1, 5);
		genBigAnswer(1, 5, 1, 5);
		genManyColors(1, 5, 1, 5);
		genAllColorsByOne(1, 5, 1, 5);
		// maxtest
		genRandom(MAXN - 5, MAXN, MAXN - 5, MAXN);
		genRandom(MAXN - 5, MAXN, 200, 500);
		genRandom(MAXN - 5, MAXN, 1, 10);
		genAllColorsByOne(MAXN - 5, MAXN, MAXN - 5, MAXN);
		genAllColorsByOne(MAXN - 5, MAXN, 200, 500);
		genAllColorsByOne(MAXN - 5, MAXN, 1, 10);
		genAllOne(MAXN - 5, MAXN, MAXN - 5, MAXN);
		genAllOne(MAXN - 5, MAXN, 200, 500);
		genAllOne(MAXN - 5, MAXN, 1, 10);
		genTwoColor(MAXN - 5, MAXN, MAXN - 5, MAXN);
		genTwoColor(MAXN - 5, MAXN, 200, 500);
		genTwoColor(MAXN - 5, MAXN, 1, 10);
		genBigAnswer(MAXN - 5, MAXN, MAXN - 5, MAXN);
		genBigAnswer(MAXN - 5, MAXN, 200, 500);
		genBigAnswer(MAXN - 5, MAXN, 1, 10);
		genManyColors(MAXN - 10, MAXN - 5, MAXN - 5, MAXN);
		genManyColors(MAXN - 10, MAXN - 5, 200, 500);
		genManyColors(MAXN - 10, MAXN - 5, 1, 10);

		for (int i = 0; i < 3; i++) {
			genRandom(1, MAXN, 1, MAXN);
			genAllOne(1, MAXN, 1, MAXN);
			genTwoColor(1, MAXN, 1, MAXN);
			genBigAnswer(1, MAXN, 1, MAXN);
			genManyColors(1, MAXN, 1, MAXN);
			genAllColorsByOne(1, MAXN, 1, MAXN);
		}
	}

	static final Random rand = new Random(12313L);

	static int[] randomPermutation(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = i;
			int j = rand.nextInt(i + 1);
			int t = a[j];
			a[j] = a[i];
			a[i] = t;
		}
		return a;
	}

	static void renum(int k, int[] a) {
		int[] p = randomPermutation(k);
		for (int i = 0; i < a.length; i++) {
			a[i] = p[a[i]];
		}
	}

	static int random(int l, int r) {
		return rand.nextInt(r - l + 1) + l;
	}

	static int random(int n) {
		return random(0, n - 1);
	}

	static void print(int n, int k, int s, int[] a) {
		renum(k, a);
		++testNum;
		System.err.println("Generating test #" + testNum);
		try {
			PrintWriter out = new PrintWriter(testNum / 10 + "" + testNum % 10);
			out.println(n + " " + k + " " + s);
			for (int i = 0; i < n; i++) {
				if (i > 0) {
					out.print(' ');
				}
				out.print(a[i] + 1);
			}
			out.println();
			out.close();
		} catch (Throwable e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	static void genRandom(int minN, int maxN, int minS, int maxS) {
		int n = random(minN, maxN);
		int k = random(Math.max(1, n >> 3)) + 1;
		int s = random(minS, maxS);
		int[] a = new int[n];
		int[] was = new int[k];
		for (int i = 0; i < n; i++) {
			a[i] = random(k);
			was[a[i]]++;
		}
		all: while (true) {
			for (int i = 0; i < k; i++) {
				if (was[i] == 0) {
					was[i]++;
					int j = random(n);
					was[a[j]]--;
					a[j] = i;
					continue all;
				}
			}
			break;
		}
		print(n, k, s, a);
	}

	static void genAllOne(int minN, int maxN, int minS, int maxS) {
		int n = random(minN, maxN);
		int k = 1;
		int s = random(minS, maxS);
		int[] a = new int[n];
		print(n, k, s, a);
	}

	static void genTwoColor(int minN, int maxN, int minS, int maxS) {
		int n = random(minN, maxN);
		if (n <= 2) {
			n += 2;
		}
		int k = 2;
		int s = random(minS, maxS);
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = random(2);
		}
		print(n, k, s, a);
	}

	static void genManyColors(int minN, int maxN, int minS, int maxS) {
		int n = random(minN, maxN);
		int k = random(MAXN - n) + n;
		int s = random(minS, maxS);
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = random(k);
		}
		print(n, k, s, a);
	}

	static void genAllColorsByOne(int minN, int maxN, int minS, int maxS) {
		int n = random(minN, maxN);
		int k = n;
		int s = random(minS, maxS);
		int[] a = randomPermutation(n);
		print(n, k, s, a);
	}

	static void genBigAnswer(int minN, int maxN, int minS, int maxS) {
		int n = random(minN, maxN);
		int k = random(1, min(n >> 1, 10));
		int s = random(minS, maxS);
		int[] a = new int[n];
		for (int i = 0; i < n;) {
			int j = i + random(2) + 1;
			int color = random(k);
			while (i < n && i < j) {
				a[i++] = color;
			}
			i = j;
		}
		print(n, k, s, a);
	}

}
